Gym

这个就是哈夫曼树哇~

我们仨英语太差了，跟榜时候才看出来是哈夫曼树雾

一个优先队列就可以搞定

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

View Code