POJ-3253 Fence Repair---Huffman贪心

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<queue>
 6 #include<vector>
 7 using namespace std;
 8 typedef long long ll;
 9 int n;
10 int main()
11 {
12     while(scanf("%d", &n) != EOF)
13     {
14         priority_queue<int, vector<int>, greater<int> >q;
15         int x;
16         for(int i = 0; i < n; i++)
17         {
18             scanf("%d", &x);
19             q.push(x);
20         }
21         ll ans = 0;
22         while(q.size() > 1)
23         {
24             int a = q.top();
25             q.pop();
26             int b = q.top();
27             q.pop();
28             q.push(a + b);
29             ans += (a + b);
30         }
31         cout<<ans<<endl;
32     }
33     return 0;
34 }