题解 | #[NOIP2004]合并果子#

思路

贪心正解。用优先队列，每次把最小的两个果子合并了，得到的是最优解。

代码

#include<bits/stdc++.h>
using namespace std;

priority_queue<int,vector<int> , greater<int> >q;
int n,a,b,ans=0;

int main(){
     scanf("%d",&n);
     for(int i=1;i<=n;i++){
         scanf("%d",&a);
         q.push(a);
    }
    while(q.size()!=1){
        a=q.top();
        q.pop();
        b=q.top();
        q.pop();
        ans+=a+b;
        q.push(a+b);
    }
    printf("%d",ans);
    return 0;   
}