题解 | #哈夫曼树#

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct treenode{
    int value;
    bool leaf;
    treenode(int x):value(x),leaf(true){};
    bool operator< (treenode y) const{
        return value>y.value;
    }
};
priority_queue<treenode> l;
vector<treenode> total;
void init(){
    while(!l.empty()) l.pop();
    total.clear();
}
int main() {
    int n;
    while(cin>>n){
        init();
        for(int i=0;i<n;i++){
            int t;
            cin>>t;
            treenode tem(t);
            l.push(tem);
        }
        while(n>1){
            n--;
           treenode a=l.top();
           l.pop();
           treenode b=l.top();
           l.pop();
           treenode c(a.value+b.value);
           c.leaf=false;
           l.push(c);
           total.push_back(c);
        }
        int r=0;
        for(int i=0;i<total.size();i++){
            if(total[i].leaf==false) r+=total[i].value;
        }
        cout<<r<<endl;
    }
    
}