题解 | 哈夫曼树

#include <iostream>
#include <queue>
using namespace std;
struct Node {
    int val;
    Node* l, * r;
    Node(int n, Node* a, Node* b) {
        val = n;
        l = a, r = b;
    }
};
struct Cmp {
    bool operator()(Node* a, Node* b) {
        return a->val > b->val;
    }
};
void f(Node* root, int& sum, int hight) {
    if (!root->l && !root->r) {
        sum += hight * root->val;
    }
    if (root->l) {
        f(root->l, sum, hight + 1);
    }
    if (root->r) {
        f(root->r, sum, hight + 1);
    }
}
int main() {
    int n;
    int sum;
    while (cin >> n) {
        sum = 0;
        int temp;
        priority_queue<Node*, vector<Node*>, Cmp>pq;
        for (int i = 0; i < n; ++i) {
            cin >> temp;
            pq.push(new Node(temp, nullptr, nullptr));
        }
        while (pq.size() != 1) {
            Node* x = pq.top();
            pq.pop();
            Node* y = pq.top();
            pq.pop();
            pq.push(new Node(x->val + y->val, x, y));
        }
        f(pq.top(), sum, 0);
        cout << sum << endl;
    }
}
// 64 位输出请用 printf("%lld")