题解 | #哈夫曼树#

//所有中间节点的权值和为带权路径长度，这个知识点很重要。剩余的就是利用小根堆（优先队列）了
#include "stdio.h"
#include "queue"
using namespace std;
struct TreeNode{
    int weight;
};

bool operator <(TreeNode lhs,TreeNode rhs){
    if (lhs.weight > rhs.weight) //父节点大于孩子时交换，相当于构建小根堆
        return true;
    else
        return false;
}

int main(){
    int n;
    while (scanf("%d",&n)!=EOF){
        priority_queue<TreeNode> myPQueue;
        for (int i = 0; i < n; ++i) {
            TreeNode node;
            scanf("%d",&node.weight);
            myPQueue.push(node);
        }
        int sum = 0;
        while (myPQueue.size()>1){
            TreeNode node1,node2,node3;
            node1 = myPQueue.top();myPQueue.pop();
            node2 = myPQueue.top();myPQueue.pop();
            node3.weight = node1.weight + node2.weight;
            sum += node3.weight;
            myPQueue.push(node3);
        }
        myPQueue.pop();
        printf("%d\n",sum);
    }
}