B1752 合并果子
B1752 合并果子
【算法标签】 贪心
【语法标签】 :cin/cout、for循环、while循环、vector、优先队列(priority_queue)
有 种果子(),第 种果子有 个()。
每次可以将两堆果子合并成一堆,消耗的体力等于两堆果子的重量之和。所有果子经过 次合并后只剩一堆。
求:最小的体力耗费总值。题目保证结果小于 。
输入格式:
- 第一行:一个整数
- 第二行: 个整数
输出格式:
- 一个整数,表示最小体力耗费值
样例:
输入:
3
1 2 9
输出:
15解释:先合并 1 和 2(耗费 3),得到新堆 3;再合并 3 和 9(耗费 12)。总耗费 = 3 + 12 = 15。
二、解题思路
数据规模分析
- : 的算法可以轻松通过,但 会超时。
- ,最终答案 :使用
int类型存储即可,不会溢出。
为什么用贪心?
这是一个经典的哈夫曼编码问题。核心观察:
越早被合并的果子堆,在后续的每次合并中都会被反复累加。 如果有一堆很大的果子(比如 100),我们第一次就把它合并进去,那么此后每次合并都要带上这 100 的代价。所以,大的堆应该尽量晚合并,小的堆应该尽量早合并。
贪心策略:每次选最小的两堆合并。
为什么一定是最优的?假设有三堆果子,重量分别为 ,考虑两种合并顺序:
先合并 和 ,再合并 和 :
先合并 和 ,再合并 和 :
两者相减:(因为 )。
所以每次选最小的两堆合并,总耗费更小。这个结论可以推广到 堆的情况。
数据结构选择:小根堆
每次需要找"最小的两堆"。如果用数组,每次找最小值需要 扫描,总复杂度 ,对于 会超时。
正确的做法:使用小根堆(优先队列)。堆顶永远是最小值,取最小值只需 ,插入新值只需 。
小根堆的 C++ 定义方式:
priority_queue<int, vector<int>, greater<int>> pq;注意第三个模板参数 greater<int> 是关键——它让堆顶变成最小值(默认是大根堆)。
手动模拟样例
以 n=3, a=[1, 2, 9] 为例,逐步模拟:
| 步骤 | 当前堆中元素 | 操作 | 消耗体力 | 累计体力 |
|---|---|---|---|---|
| 初始 | [1, 2, 9] | — | — | 0 |
| 第 1 次合并 | [1, 2, 9] | 取出 1 和 2,合并得 3,放回堆中 | 1+2=3 | 3 |
| 第 2 次合并 | [3, 9] | 取出 3 和 9,合并得 12,放回堆中 | 3+9=12 | 3+12=15 |
| 结束 | [12] | 只剩一堆,停止 | — | 15 |
算法流程
- 将 个数字全部加入小根堆。
- 重复执行,直到堆中只剩一个元素:
- 弹出堆顶,记为 (当前最小值)
- 再弹出堆顶,记为 (当前次小值)
- 将 累加到答案中
- 将 放回堆中
- 输出答案。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
// 小根堆:堆顶是最小值
// 模板参数:int=元素类型, vector<int>=底层容器, greater<int>=比较器(小的优先)
priority_queue<int, vector<int>, greater<int>> pq;
// 将所有果子数量加入堆中
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
pq.push(x);
}
int ans = 0; // 累计体力耗费
// 当堆中至少还有两堆时,继续合并
while (pq.size() > 1) {
// 取出最小的两堆
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
// 合并这两堆
int sum = a + b;
ans += sum; // 累加体力耗费
// 将合并后的新堆放回堆中
pq.push(sum);
}
cout << ans << endl;
return 0;
}大根堆 vs 小根堆 速查:
// 大根堆(默认):堆顶最大
priority_queue<int> q1; // 等价于下面
priority_queue<int, vector<int>, less<int>> q2; // less = 大的优先
// 小根堆:堆顶最小
priority_queue<int, vector<int>, greater<int>> q3; // greater = 小的优先四、复杂度分析
- 时间复杂度:。初始建堆 ,之后进行 次合并,每次合并涉及 2 次
pop和 1 次push,堆操作每次 。总计 。 - 空间复杂度:。优先队列最多同时存放 个元素。
五、知识扩展:哈夫曼树(Huffman Tree)
本题是哈夫曼编码求最小带权路径长度(WPL)的经典应用。
在哈夫曼树中:
- 叶子节点对应每一堆果子,权重就是果子数量。
- 合并过程就是自底向上构建哈夫曼树:每次选两个权值最小的节点,生成一个新的父节点(权值 = 两子节点权值之和)。
- 总耗费 = 所有非叶子节点的权值之和 = 所有叶子节点的权值乘以其到根节点的距离之和(WPL)。
现实生活中,哈夫曼编码用于文件压缩:统计文件中每个字符出现的频率,频率高的字符用短编码,频率低的用长编码。构造最优编码树的过程,就是本题的合并过程。
类似题目:ZYF040 连接木棍的最低费用(完全相同的模型,只是换了场景)。
