题解 | #哈夫曼树#

/*本题与搬水果题异曲同工，均利用小顶堆实现*/

#include <iostream>
#include <queue>
using namespace std;
int main(){
    priority_queue< int , vector<int> , greater<int> > min_heap;
    int n=0;
    int weight=0;
    int res=0;
    int first=0,second=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>weight;
        min_heap.push(weight);
    }
    while(min_heap.size()!=1){
        first=min_heap.top();
        min_heap.pop();
        second=min_heap.top();
        min_heap.pop();
        res+=(first+second);
        min_heap.push(first+second);
    }
    cout<<res<<endl;
    return 0;
}