题解 | #搬水果#

小根堆求解哈夫曼树问题

#include <iostream>
#include "queue"
using namespace std;

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        // cout << a + b << endl;
        if (n == 0) break;
        priority_queue<int, vector<int>, greater<int>> myQueue;
        while (n--) {
            int temp;
            cin >> temp;
            myQueue.push(temp);
        }
        int ans = 0;
        while (myQueue.size() >= 2) {
            int a = myQueue.top();
            myQueue.pop();
            int b = myQueue.top();
            myQueue.pop();
            ans += a + b;
            myQueue.push(a + b);
        }
        cout<<ans<<endl;
    }
}
// 64 位输出请用 printf("%lld")