洛谷P1090 合并果子

url: https://www.luogu.com.cn/problem/P1090

tag:
哈夫曼（Huffman）树 , 优先队列

思路：因为每次合并果子需要的体力值是两堆果子的重量之和，所以为了让总的体力值最小，可以使用贪心的策略，每次都只合并所有堆中重量最小的两堆。因此可以使用优先队列，每次取出两个头节点，res += 两个节点值的和，再将和的值插入到优先队列，重复这个过程直到队列中只有一个值，最后输出res即可。

代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    priority_queue<int, vector<int>, greater<int> > heap;
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int a;
        cin >> a;
        heap.push(a);
    }
    long long res = 0;
    while(heap.size() > 1)
    {
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();
        res += a + b;
        heap.push(a + b);
    }
    cout << res << endl;
    return 0;
}