题解 | #搬水果#优先级队列解决

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
#include <queue>
#include <cmath>
using namespace std;

//哈夫曼树问题

int main() {
    int n;
    priority_queue<int> que;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }
        for (int i = 0; i < n; i++) { //输入数据
            int t;
            scanf("%d", &t);
            que.push(-t);  //变成小根堆
        }
        int total = 0;
        for (int i = 0; i < n - 1; i++) { //一共n-1次合并
            int t1 = que.top();
            que.pop();
            int t2 = que.top();
            que.pop();
            total = total + t1 + t2; //消耗的体力
            que.push(t1 + t2); //把新的放入队列中
        }
        printf("%d\n", -total);
    }
}