洛谷-P1090 [NOIP 2004 提高组] 合并果子 题解
题目链接：题解：合并果子（哈夫曼编码思想）
题目大意
有 n 堆果子，每堆有一定数量的果子。每次可以合并任意两堆，消耗的体力等于这两堆果子数量之和。
目标是通过 n-1 次合并将所有果子合并成一堆，使得总消耗体力最小。
解题思路
问题本质
这是一道经典的 哈夫曼树（Huffman Tree） 构造问题。
- 每次合并两堆果子，相当于在哈夫曼树中合并两个叶子节点；
- 合并代价 = 两堆重量之和；
- 总代价 = 所有内部节点的权值之和；
- 要使总代价最小，应总是优先合并当前最小的两堆。
贪心策略：每次从所有堆中选出最小的两个进行合并，这样可以让小的数尽可能少地参与后续累加，从而最小化总代价。
数据结构选择
为了高效地获取和维护当前最小的两个元素，使用 最小堆（优先队列）：
- 初始时将所有果子堆数量加入最小堆；
- 每次取出堆顶两个最小值，合并后将新堆放回堆中；
- 累加每次合并的代价，直到只剩一堆。
时间复杂度为 O(n log n)，满足 n <= 10^4 的要求。
代码解析
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// 定义最小堆
priority_queue<int, vector<int>, greater<int>> Q;
int n, ans = 0;
cin >> n;
int val;
// 读入每堆果子数量，加入堆
for (int i = 0; i < n; i++) {
cin >> val;
Q.push(val);
}
// 不断合并最小的两堆
while (Q.size() > 1) {
int sum = 0;
sum += Q.top(); Q.pop(); // 取出最小
sum += Q.top(); Q.pop(); // 取出次小
ans += sum; // 累加体力消耗
Q.push(sum); // 将新堆放回
}
cout << ans;
return 0;
}
关键点说明
priority_queue<int, vector<int>, greater<int>>：定义最小堆；- 每次合并后新堆的重量为
sum，必须重新入堆，参与后续合并； - 总共合并 n-1 次，循环条件为
Q.size() > 1； - 最终输出
ans即为最小体力耗费值。
复杂度分析
- 时间复杂度：O(n log n)每次 pop 和 push 操作耗时 O(log n)，共进行 n-1 次合并，每次操作 2 次 pop 和 1 次 push。
- 空间复杂度：O(n)堆中最多存储 n 个元素。
常见误区
- 错误贪心：有人可能想先合并大的堆，但这样会导致小堆被多次累加，总代价反而更大。
- 使用数组排序模拟：每次排序再取前两个，复杂度 O(n^2 *log n)，会超时。
- 忽略数据范围：虽然题目保证结果小于 2^31，但中间变量仍建议用
int（因 n <=10^4, ai <=2*10^4，最大总和约 2* 10^8，在int范围内）。
总结
本题是哈夫曼编码的经典应用，核心在于理解“越早合并的果子，其重量会被累加得越多”，因此应让重量7小的果子尽早合并，以减少它们在后续合并中的重复计算。使用最小堆实现贪心策略，简洁高效，是解决此类合并优化问题的标准方法。