[NOIP 2004 提高组] 合并果子

知识点

贪心、优先队列、哈夫曼树

解题思路

把所有堆放入小根堆，每次取出最小的两堆，合并费用累加到答案，并把新堆压回，直到只剩一堆。

正确性说明

合并方案可表示成叶子权重为初始堆的二叉树，总费用是各叶子权重乘深度之和。在某棵最优树中，可通过交换使两个最小权叶子成为最深处的一对兄弟而不增加费用。把它们缩为权重之和的新叶，得到规模更小的同类最优问题，因此可反复贪心。

易错点

n=1无需合并，答案为0；每轮要取出两个元素再放回；使用long long累计；任意两堆可合并，不是环形相邻石子合并。

复杂度

时间O(n log n)，空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;priority_queue<long long,vector<long long>,greater<long long>>q;while(n--){long long x;cin>>x;q.push(x);}long long ans=0;while(q.size()>1){long long x=q.top();q.pop();long long y=q.top();q.pop();ans+=x+y;q.push(x+y);}cout<<ans<<'\n';}