# B. Villagers [문제 링크](https://codeforces.com/contest/2133/problem/B) ## Problem Statement Steve lives in a village with $n$ other villagers. Unfortunately, due to disputes over the distribution of emeralds, none of those villagers are friends with any other villager. Furthermore, villager $i$ initially has a *grumpiness* of $g_i$. Steve can perform the following operation any number of times: - Select two villagers $i$ and $j$ and give them $\max(g_i, g_j)$ emeralds to share. Both of their grumpinesses decrease by $\min(g_i, g_j)$, and they become friends with each other if they weren't already. Steve wishes to make every villager friends with every other villager (possibly through some intermediate friendships); that is, from any villager, you can follow a path of friendships to reach any other villager. Since he does not want to inflate the village economy too much, calculate the minimum number of emeralds he must give away to accomplish this. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of villagers. The second line of each test case contains $n$ integers $g_1, g_2, \ldots, g_n$ ($1 \le g_i \le 10^9$) — the initial grumpiness of each villager. It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case, output a single integer — the minimum number of emeralds Steve must give away to make everyone friends. ## 풀이 내림차순으로 정렬하여 두개씩 묶어서 그중 큰 값을 선택하면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; vector<ll> g(n); for(int i=0;i<n;i++) cin >> g[i]; sort(g.begin(), g.end(), greater<int>()); ll sum=0; for(int i=0;i<n;i+=2) sum += g[i]; cout << sum << '\n'; } } ```