题解 | #哈夫曼树#

//踩坑：1.leaf1,2 pop读取，应该先top再pop
//踩坑：2.迭代中，忘了将1，2放入priority中！
#include <cstdio>
#include<queue>


using namespace std;

int main() {
 int n;
 scanf("%d",&n);
 
 priority_queue<int>quq;        //小根堆，用相反数
 
 for(int i = 0; i<n; i++){      //小根堆建立
    int leaf;
    scanf("%d",&leaf); 
    quq.push(-leaf);
 }


    int res=0;                  //迭代结果：每次左子树都是累加的，右子树其实就加一个右结点。
    while(quq.size()>1){
        int leaf1,leaf2;
        leaf1=quq.top();
        quq.pop();
        
        leaf2=quq.top();
        quq.pop();
        quq.push(leaf1+leaf2);
        res=res+leaf1+leaf2;
    }
    printf("%d\n",-res);
}