最近在清理牛客tracker里的每日一题记录时，翻到一道“小苯的序列合并”，一眼扫过去以为是普通的合并有序数组，结果又演了半天才AC。这道题本质上是一个披着“序列合并”外衣的贪心问题，但如果不把合并代价和数据结构选对，很容易写出O(n^2)的暴力然后被极限数据教做人。这篇就从头拆一遍这题，包括题意解读、贪心证明、优先队列实现，以及我在tracker里归档时整理出来的几个变式。
1. 题目到底在说什么：小苯要合并的序列是什么
1.1 原题描述理解
“小苯的序列合并”是牛客每日一题里很典型的“阅读理解题”。我拿到的题意可以复述成下面这样：
小苯手上有一个长度为 n 的正整数序列 a，每次操作可以挑选任意两个元素合并成一个新元素，合并的花费等于这两个元素的和。合并出来的新元素会重新放回序列。问把整个序列合并成一个元素，最小的总花费是多少。
举个例子，序列是 [1, 2, 3]：
- 先合并 1 和 2，花费 3，序列变成 [3, 3]；
- 再合并两个 3，花费 6，序列变成 [6]；
- 总花费是 3 + 6 = 9。
如果换一种合并顺序：
- 先合并 2 和 3，花费 5，序列变成 [1, 5]；
- 再合并 1 和 5，花费 6，总花费 11。
显然第一种排法更优。这题要的就是在无数种合并顺序里找出最小总花费。
1.2 为什么这不是“合并两个有序数组”
很多人（包括我第一眼）看到“序列合并”四个字，会以为是把两个有序数组合并成一个有序数组的双指针题。但仔细一看，这里的“合并”是把两个元素“相加”，并且操作会反复进行，直到只剩一个元素。它的本质是哈夫曼树的构建过程，只是表现形式换成了“序列合并”。
拿上面 [1, 2, 3] 的例子来说，如果你按有序数组归并的思路去两个两个合并，得到的并不是最优解。因为有序数组归并强调“结果有序”，而这道题强调“总代价最小”，这是两套完全不同的逻辑。
1.3 样例推演与关键陷阱
牛客的样例通常给得很温和，但藏着几个关键点：
- 序列中的每个元素都会被合并多次，越早被合并的元素，越容易被后续合并再次“付费”。所以较大的数应该尽量晚参与合并，较小的数应该尽量早参与合并。
- 合并花费是累加的，不是只算最后一次。所以不能只看最后结果，要看全过程的和。
- 数据范围通常很大（比如 n 可以到 10^5，a_i 可以到 10^5），所以任何 O(n^2) 的做法都会超时。
有一个经典反例：序列 [5, 5, 5, 5]。
- 如果每次随便合并，最坏可能：5+5=10，10+5=15，15+5=20，总花费45；
- 如果按最优贪心：5+5=10，另一个5+5=10，然后10+10=20，总花费40。
差距不是很大，但如果数据规模放大，错误策略带来的额外代价会非常可观。
2. 从暴力模拟到贪心：为什么每次合并两个最小值最优
2.1 暴力思路的时间复杂度
最容易想到的暴力做法是：每次在所有元素中找到最小的两个，把它们合并，把结果放回，重复 n-1 次。每次找最小需要扫描一遍，复杂度 O(n)，总共 O(n^2)。对于 n=10^5 的数据规模，大约要执行 10^10 次操作，基本跑不出来。
更“暴力”的做法是枚举所有合并顺序，也就是 n 个元素的括号化方案数量，这是卡特兰数级别，n 稍微大一点就是天文数字。所以必须找规律。
2.2 贪心选择性的数学证明
贪心策略很直观：每次选当前最小的两个元素合并。为什么它是最优的？这里可以借助“合并树”来理解。
把每次合并看作构建一棵二叉树：叶子节点是原始元素，内部节点的值等于它两个孩子节点值之和，整棵树的根节点的值就是所有元素的总和，这是固定不变的。而“总花费”是什么？是除了根节点以外所有内部节点的值之和。进一步观察，每个叶子节点对总花费的贡献等于“该叶子节点的值 × 它在树中的深度”。比如 [1,2,3] 按最优合并，树结构是：
- 3 = 1 + 2 这个内部节点深度为1（根），1和2这两个叶子深度为2；
- 根是 6 = 3 + 3，另一个叶子3深度为1。
总花费 = 1×2 + 2×2 + 3×1 = 9，和之前算的结果一致。
所以问题等价于：给 n 个叶子赋深度（深度从1开始计），每个叶子被合并的次数等于深度减1，要求构造一棵二叉树，使得 sum(value[i] × depth[i]) 最小。这就是经典的哈夫曼编码优化问题。哈夫曼算法的核心是：每次把权值最小的两个叶子合成一个权值为两者之和的新叶子，反复操作。这正好对应贪心策略。
因此这个贪心是正确的，不是碰巧，而是数学上可证明的。证明思路可以用交换论证：如果存在一个最优合并树中，某个深度较浅的叶子权值大于另一个深度较深的叶子权值，交换两者位置会使总权值变小，从而原树不是最优。所以最优解一定是权值小的叶子深度尽可能大，权值大的叶子深度尽可能小。而每次合并两个最小值，本质上就是在让最小的元素尽可能多地被合并（深度大）。
2.3 用二叉堆维护动态最小值
贪心策略确定后，剩下的问题就是高效维护“当前最小值”。每次合并后，序列会插入一个新元素，同时删除两个旧元素。这种动态最小值的维护，最自然的数据结构就是优先队列（二叉堆）。
- 初始时把所有元素加入小根堆；
- 每次从堆顶弹出两个元素 a 和 b；
- 花费累加 a+b；
- 把 a+b 放回堆里；
- 重复直到堆里只剩一个元素。
时间复杂度是 O(n log n)，空间复杂度 O(n)。这个复杂度对于 n=10^5 的数据完全够用。
3. 优先队列实现的完整代码与边界处理
3.1 C++ 实现
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; priority_queue<long long, vector<long long>, greater<long long>> pq; for (int i = 0; i < n; i++) { long long x; cin >> x; pq.push(x); } long long ans = 0; while (pq.size() > 1) { long long x = pq.top(); pq.pop(); long long y = pq.top(); pq.pop(); long long sum = x + y; ans += sum; pq.push(sum); } cout << ans << endl; return 0; }这段代码非常短，但有几个关键点必须注意。
3.2 Python 实现
import heapq n = int(input()) a = list(map(int, input().split())) heapq.heapify(a) ans = 0 while len(a) > 1: x = heapq.heappop(a) y = heapq.heappop(a) s = x + y ans += s heapq.heappush(a, s) print(ans)Python的heapq默认是小根堆，所以直接用来找最小值。这里有个性能细节：如果元素个数很多，不要用min()去反复找，那样会退化到 O(n^2)。
3.3 整型溢出与long long的坑
这是我在牛客tracker里特意标注过的问题。看题目给的 a_i 范围，如果最大值是 10^5，n 是 10^5，那么最终答案可能是什么量级？
所有元素最后都会汇总到根节点，根节点的值是 sum(a)，是原始总和的级别，最大 10^10，已经超过 int 的 2^31-1（约 2.1×10^9）。而总花费是每个内部节点值累加，最坏情况下可能达到 sum(a) × depth，其中 depth 最多 n，所以答案可能达到 10^15 级别，必须用 long long。
C++ 里如果忘了用long long而用了int，会在极端数据下爆掉，出现错误的负数。我在本地测试时用了一个 n=100000、所有数都是 100000 的用例，算出来大概是 10^15 左右，用 int 直接溢出。所以优先队列里的元素类型、累加变量统统要开long long。Python 没有这个问题，但 C++ 一定要警惕。
3.4 边界情况的测试
测试时建议自己构造几个用例：
- n=1：不需要合并，答案是0。代码里while循环不进去，正确输出0。
- n=2：两个数合并一次，答案就是两个数之和。比如 [7, 9]，答案是16。
- 所有数相等：比如 [3,3,3,3]，按贪心：3+3=6，3+3=6，6+6=12，总花费24，和公式 sum × (log2 n 向上取整？) 不一定，但至少是正确的。
- 数据很大：验证是否会超时和溢出。
4. 牛客tracker记录：我把刷题轨迹变成复盘资产
4.1 tracker里如何标注这题
我习惯在牛客tracker里给每日一题做标签，方便后面复习。这题的标签我会打上：贪心、优先队列、哈夫曼。
建议在备注里写一句“不能按有序数组合并理解，本质是加权路径长度最小化”。这句话看似简单，但过一个月再看，能帮你省下重新读题的时间。
4.2 同类变体与扩展
“序列合并”这个主题其实有一大家子变体，我在tracker里顺手整理了一个对照表：
| 题型 | 合并规则 | 解法 | 复杂度 |
|---|---|---|---|
| 任意两个元素合并，代价为和 | 哈夫曼树 | 贪心+优先队列 | O(n log n) |
| 相邻两个元素合并，代价为和 | 石子合并 | 区间DP | O(n^3) 可优化到 O(n^2) |
| 相邻两个元素合并，代价为两者较大值 | 合并后较大值 | 单调栈/区间DP | 视情况 |
| 两个有序数组合并为一个有序数组 | 双指针 | 归并 | O(n) |
如果你的目标是面试或竞赛，建议把“任意合并”和“相邻合并且只能相邻”区分清楚。很多新手在做“石子合并”时套用哈夫曼贪心，结果答案是错的。因为哈夫曼允许任意两个元素结合，而“石子合并”只允许相邻结合，局部最优不构成全局最优，必须用区间DP。
4.3 一题多解对比：贪心 vs 区间DP
“小苯的序列合并”允许任意选两个数合并，所以贪心是对的。但如果你把题目改一个条件：“每次只能合并相邻的两个数”，那么问题就从哈夫曼树变成了石子合并，需要用区间DP求解。
这两者的区别很值得品：
- 哈夫曼树：每次选全局最小的两个，用优先队列维护，O(n log n)；
- 石子合并：每次只能合并相邻的，dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum(i,j)，O(n^3)。
我在tracker里会把这两个放到一起复习，因为它们名字都叫“序列合并”，但解法完全不同。刷题的时候最怕的就是“名字相似，思路被带偏”。所以看到“合并”先确认限制条件：任意选还是相邻选？合并的代价是什么？合并结果参与下一次合并？这三个问题决定了解法方向。
5. 从每日一题到竞技刷题：这道题带来的几个习惯
5.1 先推复杂度再写代码
我写这题的时候第一版其实是用vector加sort的：每次排序取前两个，合并后再sort。n=1000可以过，n=100000直接超时。后来在 tracker 的耗时记录里看到这题的数据范围，才意识到要用堆。
这个教训是：拿到题先看数据范围。n≤100可以随便DFS，n≤5000可以O(n^2)，n≤10^5就得O(n log n)或更优。“序列合并”这种题，n一上来就是10^5，几乎明示你要用优先队列或类似log级别数据结构。
5.2 证明与直觉同样重要
有时候贪心策略一眼就能猜出来，但为什么不假思索地相信它？因为在竞赛里，“猜”和“证明”是两回事。很多贪心看起来对，实际是错的。比如“每次挑最大的数和最小的数合并”在某些变形里可能更优，但在这里就不是。
我的习惯是：在tracker的“思路”栏里写下一句话证明。比如这题，我会写：“把合并过程看成二叉树，总花费等于sum(叶子深度×权值)，最小化这个和等价于构造哈夫曼树，而哈夫曼树通过每次合并两个最小节点得到。”这句话是核心，比背代码有价值得多。
5.3 模板代码要背到肌肉记忆
优先队列维护哈夫曼树的写法非常固定，几乎是竞赛入门必背模板。C++的greater<long long>和Python的heapq都要做到闭着眼睛能写。这题的价值之一就是把堆的操作练熟：pop两次、加起来、push一次。这三个动作构成了很多贪心优化的基础。
我在刷这题之后，还顺手复习了“数据流中的中位数”“最小K个数”这些同样依赖堆的题目，发现它们的内核都是“动态维护有序性”。一件刷题的小事，最后串起了一类题，这是tracker最大的价值。
6. 这段刷题经历带给我的几个额外体会
最后分享几个题之外的东西。
第一，题目里的“小苯”这种拟人化主角，在牛客上很常见。它们通常不会增加题面理解难度，反而会让人多读几遍，这时别嫌烦，读清楚总比瞎猜好。第二，每日一题的价值在于“持续”，而不是“一天刷十道”。今天吃透这题，比一天看十道题但每题都半懂不懂，要有效得多。
第三，常备一个自己的“错题本”，哪怕是跟踪表里的一行备注。比如我为了这题写过这样一行：“先写暴力，再写优化；暴力不是白写，它是验证贪心/DP正确性的对照样例。”后来我做别的贪心题时，也确实靠暴力小数据对拍找出了好几处边界错误。
现在再看到“序列合并”这种题，我不会再被名字迷惑，而是先画一棵合并二叉树，再决定用堆还是用区间DP。这种“见招拆招”的感觉，就是靠每天积累下来的。如果你也在牛客刷每日一题，建议把tracker里的备注写详细一点，三个月后回头看，你会感谢那个愿意多写两句话的自己。
