acwing148. 合并果子
原题链接：https://www.acwing.com/problem/content/150/
思路
贪心使用集合角度思考，需要去证明最优解在某个集合的子集之中，其他的子集就可以摒弃掉。
这个题使用贪心来考虑。
我们可以发现，每次合并两堆，然后形成一个新的堆，再去找两堆合并...反复。这个合并的过程就像一颗二叉树。
比如样例，先合并1和2，再合并3和9，最后总代价就是3+12 = 15，这个合并过程就是一颗二叉树。
其实总代价最小取决于每个叶子结点到达根节点的距离。
1 * 2 + 2 * 2 + 1 * 9 = 15,所以总的代价是和树的形态有关的，最小的代价就是huffman树(带权最优树)
接下来使用贪心来解这道题。
猜想：每两次合并最小的两堆，最后的总代价最小
看下图的集合，接下来去证明最优解在左边这个子集中
证明完最优解在左边的子集之后，就可以第一步先合并两个最小的，然后递归去做就可以了。
假设下图是"其他"这个子集合并的情况
如果最小的两个在同一层，最小的这两个是a、c，那么如果交换b和c进行交换总代价是不变的(b和c到达根节点的距离没有改变)，所以交换之后就是合并了两个最小的，"合并两个最小的"是最优解，虽然这个其他情况这个时候(最小两个在同一层)中存在最小的代价，但是可以转换成合并两个最小(b和c交换)，因此最小代价是在左边子集的，最优解是在左边的子集中的
如果两个最小的没有在同一层。比如两个最小的是a、d，那么将d和b交换。
交换前(其他叶子结点a、c等等到达根节点距离没变，代价都不变，所以只看d和b的代价变化)代价是
=> d * L1 + b * L2
交换之后代价变成了
=> b * L1 + d * L2 。
交换前的代价-交换后的代价：
L1 < L2 ,d < b
L1 * (d-b) + L2 * (b-d) = (L1-L2) * (d-b) > 0
交换前的代价比交换后的代价大，所以交换进行之后代价变小，因此这个"其他"子集的代价更大,最小代价是在左边子集的，最优解是在左边的子集中的。
"最优解是在左边的子集中的"得证。
那我们要维护一个哈夫曼树，其实只需要一个小根堆就可以了(可以取最小值，删除最小值，插入值)。最后时间复杂度为\(O(nlogn)\)(小根堆存取操作是logn,要进行n次，所以nlogn)
使用小根堆，每次取出两个最小的，将其合并,记录代价，再存入小根堆。
代码
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
priority_queue<int,vector<int>,greater<int>> heap; // 小根堆
while(n --)
{
int x;
scanf("%d",&x);
heap.push(x);
}
int 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);
}
printf("%d",res);
return 0;
}