很经典的一道题了orz 记得一年多前刚学c++的时候就做过,当时用的是multiset
贪心解法就是每次找最小的合并,这里给出三种实现,挑喜欢的用吧~
(居然没有人写O(n),大概是数据太水了)
优先队列(huffman树)
个人感觉这种写起来最舒服 复杂度O(nlogn)
运行时间:116ms
#include<bits/stdc++.h>
using namespace std;
int n,a;
long long ans;
priority_queue<int,vector<int>,greater<int>> q;
int main(){
cin>>n;
for(int i=1;i<=n;i++){scanf("%d",&a);q.push(a);}
for(int i=1;i<n;i++){
int x1=q.top();q.pop();
int x2=q.top();q.pop();
ans+=x1+x2;q.push(x1+x2);
}
cout<<ans<<endl;
return 0;
}
multiset/平衡树
multiset用起来太蛋疼了(注意不是set) 复杂度O(nlogn)
什么时候打个平衡树试试(咕咕咕)
运行时间:104ms
#include<bits/stdc++.h>
using namespace std;
int n,a;
long long ans;
multiset<int> s;
int main(){
cin>>n;
for(int i=1;i<=n;i++){scanf("%d",&a);s.insert(a);}
for(int i=1;i<n;i++){
int x1=*s.begin();s.erase(s.begin());
int x2=*s.begin();s.erase(s.begin());
s.insert(x1+x2);
ans+=x1+x2;
}
cout<<ans<<endl;
return 0;
}
桶排序+队列模拟(O(n)解法)
可以发现这题值域比较小,可以考虑把每个值存到一个cnt数组里,这样就在O(n)时间内完成了排序
受到这题 的启发,我们发现每次合并完成后,堆里果子的数量一定是单调递增的。考虑用一个队列存原来每堆果子数,另一个队列存合并完堆里的果子数,每次取最小值合并。
如果值域比较大的话可以考虑基数排序,效率比快排高
运行时间:32ms(3倍!)
#include<bits/stdc++.h>
using namespace std;
int n,a,cnt[20009],Max;
long long ans;
queue<int> q1,q2;
int main(){
cin>>n;
for(int i=1;i<=n;++i){scanf("%d",&a);Max=max(a,Max),cnt[a]++;}
for(int i=1;i<=Max;++i)
while(cnt[i]--)q1.push(i);
for(int i=1,x1,x2;i<n;++i){
if(q2.empty()||!q1.empty()&&q1.front()<q2.front()){x1=q1.front();q1.pop();}//我是个沙茶,之前把q1.empty()写成了q1.front()
else{x1=q2.front();q2.pop();}
if(q2.empty()||!q1.empty()&&q1.front()<q2.front()){x2=q1.front();q1.pop();}
else{x2=q2.front();q2.pop();}
q2.push(x1+x2);ans+=x1+x2;
}
cout<<ans<<endl;
return 0;
}
orztql%%%%%%%%%%%
优化版本的if判断是不是得在!q1.empty()&&q1.front()<q2.front()这两边再加一个括号。
可以不加,&&优先级比||更高
膜
拜