AcWing 148. 合并果子

题面：
把所有的果子合成一堆：每一次合并，可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。
达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。
假定每个果子重量都为 \(1\)，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。

原题链接：148. 合并果子 - AcWing

哈夫曼树带权路径长度(WPL)

结点的带权路径长度：树的根结点到该结点的路径长度和该结点权重的乘积；
树的带权路径长度：一棵树中的所有叶子结点的带权路径长度之和。

小根堆与优先队列

使用小根堆维护所有果子，每次弹出堆顶最少的两堆果子，并将其合并，合并之后将两堆重量之和再次插入小根堆中。每次操作会将果子的堆数减 \(1\)，一共操作 \(n−1\) 次即可将所有果子合并成 \(1\) 堆。——y总

priority_queue <int, vector<int>, greater<int>>

• 存储的元素类型为int
• 使用vector<int>作为底层容器类型
• greater<int>作为函数对象，指定元素之间的比较方式

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int main()
{
	int n;
	cin >> n;
	priority_queue<int, vector<int>, greater<int>> heap;
	while (n--) {
		int x;
		cin >> x;
		heap.push(x);
	}
	int wpl = 0;
	while (heap.size() > 1) {
		int t1 = heap.top();
		heap.pop();
		int t2 = heap.top();
		heap.pop();
		heap.push(t1 + t2);
		wpl += t1 + t2;
	}
	cout << wpl;
}