洛谷-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 个元素。

常见误区

1. 错误贪心：有人可能想先合并大的堆，但这样会导致小堆被多次累加，总代价反而更大。
2. 使用数组排序模拟：每次排序再取前两个，复杂度 O(n^2 *log n)，会超时。
3. 忽略数据范围：虽然题目保证结果小于 2^31，但中间变量仍建议用 int（因 n <=10^4, ai <=2*10^4，最大总和约 2* 10^8，在 int 范围内）。

总结

本题是哈夫曼编码的经典应用，核心在于理解“越早合并的果子，其重量会被累加得越多”，因此应让重量7小的果子尽早合并，以减少它们在后续合并中的重复计算。使用最小堆实现贪心策略，简洁高效，是解决此类合并优化问题的标准方法。