题解 | #搬水果#优先队列解法

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    while(cin>>n){
        if(n==0)return 0;
        priority_queue<int,vector<int>,greater<int>>q;
        while(n--){
            int temp;cin>>temp;
            q.push(temp);
        }
        int res=0;
        while(q.size()!=1){
            int t1 = q.top();q.pop();
            int t2 = q.top();q.pop();
            res+=t1+t2;
            q.push(t1+t2);
        }
        cout<<res<<endl;
    }
}
// 64 位输出请用 printf("%lld")

本题实质上是构造哈夫曼树。

c++提供了优先队列priority_queue。默认自动把元素排成从大到小。

要让他从小到大，需要priority_queue<int, vector<int>, greater<int>>q。

这样创建的q就是默认从小到大排序