懒惰的小明 STL 优先队列实现 数据结构中的哈弗曼
懒省事的小明
#include<cstdio>#include<set>using namespace std;int main(){ int n; multiset<int> set1; while(scanf("%d",&n)!=EOF) { while(n--) { set1.clear(); int m; scanf("%d",&m); for(int i=0;i<m;i++) { int a; scanf("%d",&a); set1.insert(a); } long long sum=0; while(set1.size()!=1) { int a=*set1.begin(); set1.erase(set1.begin()); int b=*set1.begin(); set1.erase(set1.begin()); int c=a+b; sum+=c; set1.insert(c); } printf("%lld\n",sum); } } return 0;}#include<iostream>#include<algorithm>#include<queue>#define N 100using namespace std;int main(){ long long test,n,i,t,tt,ans; priority_queue<long long, vector<long long >, greater<long long> >pq; cin>>test; while(test--) { while(!pq.empty()) pq.pop(); cin>>n; for(i=0; i<n; i++) { cin>>t; pq.push(t); } ans=0; while(!pq.empty()) { t=pq.top(); pq.pop(); if(pq.empty()) { break; } else { tt=pq.top(); pq.pop(); tt=tt+t; ans+=tt; pq.push(tt); } } cout<<ans<<endl; } return 0;}
#include<iostream>#include<algorithm>#include<queue>#define N 100using namespace std;int main(){ long long test,n,i,t,tt,ans; priority_queue<long long, vector<long long >, greater<long long> >pq; cin>>test; while(test--) { while(!pq.empty()) pq.pop(); cin>>n; for(i=0; i<n; i++) { cin>>t; pq.push(t); } ans=0; while(!pq.empty()) { t=pq.top(); pq.pop(); if(pq.empty()) { break; } else { tt=pq.top(); pq.pop(); tt=tt+t; ans+=tt; pq.push(tt); } } cout<<ans<<endl; } return 0;}