1 条题解

  • 0
    @ 2026-11-16 20:48:26

    最小合并账本 · 讲解

    思路与接口

    n 组最终变为一组,合并次数总是 n−1。因此固定手续费的总贡献必定是 (n−1)f,不会改变最优合并顺序。其余费用是每次合并的重量和。每次取当前最小的两组,合并后把它们的重量和放回,即可得到最小总费用。

    用 priority_queue<long long, vector<long long>, greater<long long>> 建立小根堆。每轮用 top()、pop() 取两次最小值,用 push(x+y) 放回新重量,将 x+y+f 加到答案。注意放回堆的是 x+y,不包含 f。当堆中只有一组时结束,n=1 时循环一次也不会执行。

    为什么贪心正确

    把一个完整合并方案画成二叉树:初始各组是叶子,每次合并是内部节点,根表示最后一组。每组重量对费用的贡献等于其重量乘以叶子深度;手续费是每个内部节点贡献 f,合计固定。

    在一棵最优树中,可选择最深的一对兄弟叶子。将两组最小重量放在这两个最深位置不会增加加权深度和:若较小重量原来更浅、较大重量更深,交换它们的费用变化为 (小−大)×(深−浅)≤0。依次交换后,存在一个最优方案,使当前最小的两组成为兄弟并先合并。

    把这对兄弟缩成一个重量为 x+y 的叶子,剩余问题正是规模减一的同类问题。由此反复应用同一选择,每次合并最小两组的方案是最优的。零重量和并列最小值也满足这个交换论证。

    复杂度与整数范围

    建立堆后进行 n−1 次合并,总时间 O(n log n),空间 O(n)。新组重量最大可达 200000×10⁹,答案更大,所以初始重量、合并重量、手续费与总费用均使用 long long,不能只在最终输出时转换。

    常见错误

    • 使用默认大根堆,先合并最大的两组。
    • 将手续费加入新重量,导致同一笔手续费在后续合并中反复计费。
    • 用 int 存合并重量或答案。配套错误程序保留这种真实的整数溢出错误,大重量与高手续费数据能拒绝它。
    • n=1 仍尝试取出两组,或错误收取一次手续费。

    独立验证

    对 n≤8,Python 子集 DP 枚举合并树根的所有两部分划分:dp[S]=min(dp[A]+dp[S\A]+sum[S]+f),单元素集合费用为 0。仅要求 A 包含 S 的最低位以避免重复划分,并没有使用贪心假设。200 次小规模测试同时对照此枚举值、Python heapq 贪心值和 C++ 输出;正式大数据由独立 Python heapq 实现计算。

    原创来源记录

    本题题面、样例、代码、讲解与数据从零编写。只使用公开的算法概念和 C++ 标准库接口,没有使用第三方题面、故事、程序或测试文件。

    C++17 参考实现

    #include <functional>
    #include <iostream>
    #include <queue>
    #include <vector>
    using namespace std;
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        int n;
        long long fee;
        cin >> n >> fee;
        priority_queue<long long, vector<long long>, greater<long long>> weights;
        for (int i = 0; i < n; ++i) {
            long long x;
            cin >> x;
            weights.push(x);
        }
        long long answer = 0;
        while (weights.size() > 1) {
            long long x = weights.top();
            weights.pop();
            long long y = weights.top();
            weights.pop();
            long long merged = x + y;
            answer += merged + fee;
            weights.push(merged);
        }
        cout << answer << '\n';
    }
    
    
    • 1

    信息

    ID
    5262
    时间
    2000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    1
    已通过
    1
    上传者