当前位置：首页 > 提高组 > 2004年NOIP提高组合并果子（洛谷P1090）题解：优先队列与贪心算法的完美应用

2004年NOIP提高组合并果子（洛谷P1090）题解：优先队列与贪心算法的完美应用

4个月前 (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变量累计每次合并的消耗，最终结果即为最优解。