跳到主要内容

AcWing 148. 合并果子

本节目标

每次合并当前最轻的两堆果子，用小根堆实现最小总代价的 Huffman 式贪心。

这是局部约束与构造中最小代价合并的拓展母题。

题意与约束​

每次选择两堆果子合并，代价等于两堆重量之和，合并后成为一堆。求合成一堆的最小总代价。

直接思路与瓶颈​

枚举每一步选择会产生大量合并顺序。较重的中间堆若过早生成，会在后续被重复计费，代价通常更大。

贪心模型与算法推导​

每次取当前最小的两堆合并，把新堆放回集合。小根堆支持重复地取出两个最小值与插入新值。

正确性依据​

两堆最小权重可在某个最优合并树中作为最深的一对兄弟；若更重的叶子位于更深处，与较轻叶子交换不会增大总代价。先合并两最小堆后，剩余问题仍是同一形式，故可递归应用该选择。

样例执行过程​

[1,2,9] 先合并 1+2=3，总代价为 3；堆变为 [3,9]，再合并得到 12，总代价 15。

代码实现​

C++17
#include <functional>
#include <queue>
#include <vector>
using namespace std;

long long minMergeCost(vector<int> weights) {
    priority_queue<long long, vector<long long>, greater<long long>> heap(weights.begin(), weights.end());
    long long answer = 0;
    while (heap.size() > 1) {
        const long long merged = heap.top(); heap.pop();
        const long long second = heap.top(); heap.pop();
        answer += merged + second;
        heap.push(merged + second);
    }
    return answer;
}

复杂度分析​

进行 n-1 次堆操作，时间 O(n log n)；堆占用 O(n) 空间。

边界与易错点​

  • 只有一堆时无需合并，代价为 0。
  • 必须是小根堆，不能每轮选择两堆最大的果子。
  • 累计代价使用较宽整数类型更稳妥。

模式迁移​

最优编码、文件合并和木板切割等“中间结果会再次计费”的问题，常对应每次合并两个最小权重的模型。