题解 | 哈夫曼树

#include <stdio.h>
#include <string>
#include <queue>
using namespace std;
int main() {
    priority_queue<int> pqueue;//存储权值的相反数
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int leaf;
        scanf("%d", &leaf);
        pqueue.push(-1*leaf);
    }
    int weight = 0;
    while (pqueue.size() >= 2) {
        int leaf1 = pqueue.top();
        pqueue.pop();
        int leaf2 = pqueue.top();
        pqueue.pop();
        weight += leaf1 + leaf2;
        pqueue.push(leaf1 + leaf2);
    }printf("%d\n", -1 * weight);

        return 0;
}