1 条题解
-
0
最小合并账本 · 讲解
思路与接口
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
- 上传者