2004年NOIP提高组合并果子（洛谷P1090）题解：优先队列与贪心算法的完美应用
6个月前 (08-24)
一、题目解读
合并果子（洛谷P1090）是2004年NOIP提高组的一道经典题目，原题链接：https://www.luogu.com.cn/problem/P1090。题目描述了一个果园场景：需要将N堆果子合并成一堆，每次合并消耗体力为两堆果子的重量之和，目标是通过设计合并顺序，使总消耗体力最小。数据范围要求1≤N≤10000，每堆果子重量1≤ai≤20000，需输出最小体力值。
二、解题思路
核心思路为贪心算法：每次优先合并当前最小的两堆果子，以降低后续合并的消耗。实现关键在于利用**优先队列（最小堆）**自动维护果子堆的重量排序，确保每次取出的两堆果子重量最小，从而保证整体消耗最优。该策略符合哈夫曼树（最优二叉树）的构建思想，即权值小的节点优先靠近叶节点，减少路径长度。
三、解题步骤
1. 输入处理：读取果子种类数N及每堆重量，存入优先队列q（小顶堆）。
2. 合并过程：
○ 循环直至队列仅剩一堆：
弹出队首两堆果子a、b，计算合并消耗sum += a + b；
将新堆a+b重新入队q，维持堆有序性。
3. 输出结果：最终sum即为最小体力消耗值。
四、代码与注释
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n, sum = 0;
cin >> n; // 输入果子种类数N
// 创建小顶堆优先队列，自动维护元素升序
priority_queue<int, vector<int>, greater<int>> q;
for(int i = 0; i < n; ++i) {
int weight;
cin >> weight; // 输入每堆果子重量
q.push(weight); // 初始化堆
}
while(q.size() > 1) { // 循环至仅剩一堆
int a = q.top(); q.pop(); // 取出最小两堆果子
int b = q.top(); q.pop();
sum += a + b; // 累加当前合并消耗
q.push(a + b); // 新堆入列
}
cout << sum << endl; // 输出最小体力值
return 0;
}注释解析：
● 优先队列q通过greater<int>参数指定为小顶堆，确保q.top()始终返回当前最小重量堆。
● 循环条件q.size() > 1保证合并次数为N-1，符合题目要求。
● sum变量累计每次合并的消耗，最终结果即为最优解。
五、总结
本解法通过贪心策略与优先队列的结合，将复杂度为O(NlogN)的合并问题高效解决。关键在于“局部最优（每次最小合并）导致全局最优”的证明，体现了贪心算法的核心思想。实际应用中，该思路可扩展至类似资源合并优化场景，如哈夫曼编码树的构建。代码简洁且符合竞赛要求，是学习优先队列与贪心算法的经典案例。
原创内容 转载请注明出处
