思路
若从最大堆开始合并,则合并后还要带着合并后的堆再合并其他堆,这样的话,这个最大堆就会累加到最终答案里面,显然会增大最后答案,所以策略是:每次都合并最小的两个堆,直到变成一个堆停止。
根据思路,你会发现需要不停地动态取最小值,优先队列最合适取出前K个最小(或最大)的数。
#include <cstdio>
#include <queue>
using namespace std;
int n,ans;
priority_queue<int,vector<int>,greater<int> >q;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
int t;
scanf("%d",&t);
q.push(t);
}
while(q.size()>=2){
int a=q.top();q.pop();
int b=q.top();q.pop();
ans+=a+b;
q.push(a+b);
}
printf("%d\n",ans);
return 0;
}
瑞瑞的木板
思路:如果假设现在已经按要求拆完,要求再按最少力气合并成一块木板,条件不变,是不是就变成“合并果子”了?我们可以动态合并2个最小,但动态的把一块木板拆分却很难。所以干脆逆向思维,倒过来用最小的力气把拼成一块,这样和用最小力气拆开是一样的。
算一下答案
最差情况是,单块木板都是$5\cdot 10^4$,最大共有$2\cdot 10^4$个木板,第一块木板要n次,第二块是n-1次,依次类推,总共力气=$5\cdot 10^4 \cdot (n^2-n+1) \approx 10^{12}$,超int了,需要改为long long类型。
#include <cstdio>
#include <queue>
using namespace std;
int n;
long long ans;
priority_queue<int,vector<int>,greater<int> >q;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
int t;
scanf("%d",&t);
q.push(t);
}
while(q.size()>=2){
int a=q.top();q.pop();
int b=q.top();q.pop();
ans+=a+b;
q.push(a+b);
}
printf("%lld\n",ans);
return 0;
}