NOIP 2004 提高组 P1090合并果子：从暴力枚举到优先队列的算法进化

一、问题本质分析

合并果子问题要求找到将所有果子堆合并为一堆的最小体力消耗值，本质上是一个构建最优二叉树的问题。每次合并消耗的体力等于两堆果子的重量之和。

二、C++优先队列解法

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, sum = 0;
    cin >> 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;
}

三、算法核心思想

1. 贪心策略：每次合并最小的两堆，确保局部最优导致全局最优

2. 数据结构：使用小顶堆（优先队列）实现O(logn)的取最小值操作

3. 复杂度分析：O(nlogn)时间复杂度，O(n)空间复杂度

四、新手学习路径

1. 先理解二叉树合并过程

2. 手动模拟n=3的简单案例

3. 比较暴力解与优先队列解的区别

4. 思考为什么不能使用简单的排序解法

五、常见误区警示

1. 错误使用大顶堆导致结果偏大

2. 未考虑整数溢出问题（本题数据范围无需处理）

3. 忘记最后剩余单堆的特殊情况