[NOIP2004]合并果子 优先队列

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
// 定义全局变量
ll n, a, b, kkk;
// 优先队列，使用最小堆
priority_queue<ll, vector<ll>, greater<>> q;
int main() {
    // 读取输入的整数n
    cin >> n;
    // 循环读取n个整数并加入优先队列
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        q.push(x);
    }
    // 当优先队列中元素个数大于1时，执行以下操作，及合并为一个果子时
    while (q.size() > 1) {
        // 取出优先队列中的最小元素a
        a = q.top();
        q.pop();
        // 取出优先队列中的次小元素b
        b = q.top();
        q.pop();
        //以上为取出两个果子并合并的最小体力值
        // 将a和b的和累加到kkk中,及合并两个果子体力耗费值
        kkk += (a + b);
        // 将a和b的和重新加入优先队列，及合并两个果子后新果子体力值
        q.push(a + b);
    }
    // 输出最终结果kkk
    cout << kkk << endl;
    return 0;
}