洛谷 P1672 这道题光看题面很容易被绕进去——“围栏”、“切割”、“长度”好像就是一道模拟切割过程的题。但刷过类似题的朋友应该已经闻到味了这道题的本质其实是经典的 Huffman 合并问题。和洛谷 P1090 合并果子几乎是一个模子刻出来的区别只在包装方式。我做这道题的时候第一反应也是傻乎乎地去模拟切木板结果样例都过不了。后来把思路反过来想一下就通了。这篇文章就把我的完整推导过程、贪心证明、代码实现和踩坑记录都放出来希望能帮到正在卡这道题的人。1. 题意与核心模型拆解1.1 原题到底在说什么题目说的是有一根长木板长度固定需要切成 n 段每段的长度已经给定了比如要切成 3 段长度分别是 8、5、8。切割有个规矩每次切一刀费用等于当前这块木板的总长度。注意这里不是每切一刀固定收多少钱而是按被切木板本身的长度收费。举个例子一根长度为 21 的木板要切成 8、5、8 三段。如果第一刀把 21 切成 13 和 8费用就是 21。剩下 13 那根再切成 8 和 5费用是 13。总费用 34。但如果第一刀把 21 切成 16 和 5第二刀把 16 切成 8 和 8总费用就是 21 16 37。同样的三段切割顺序不同花的钱就不一样。题目让你求最小总费用。很多人第一眼看到这个题会以为要动态规划毕竟是个最优化问题。但其实这题有个非常漂亮的转化把“切”反过来看变成“拼”。既然切木板是长木板一分为二那反过来就是把若干小木板一段一段拼回那根长木板。每次拼两段费用等于这两段长度之和。这样问题就变成了有 n 个长度已知的小木板每次任选两块拼在一起代价是这两块的长度之和问把 n 块合成一整块木板的最小总代价。这个转化很关键因为它把一个“未知目标拆成已知片段”的优化问题变成了“把已知片段合并成整体”的合并问题。1.2 为什么“切木板”和“合并果子”是同一道题做过 P1090 合并果子的人应该已经看出来了这就是同一道题。合并果子的题意是有 n 堆果子每次合并两堆代价是两堆重量之和求最小总代价。这跟“把 n 段木板拼起来”在数学上完全等价连数据范围都懒得换。我当时就是被“切割”这两个字误导了在“正着切”的路上越走越远。实际上正着切你很难找到一个好的贪心策略因为每次切哪里会改变之后所有块的大小而且你也不知道哪一刀是“赚”的。但是倒着拼问题就清晰多了每次合并的两段木板它们各自在后续的每次合并中都会被继续计入费用所以长度越短的木板越应该被“深藏”在合并过程的下层越晚参与那些产生大费用的合并。这也是 Huffman 编码的核心思想让权值小的叶子拥有更长的路径权值大的叶子拥有更短的路径从而让整棵树的加权路径长度最小。所以这道题其实考两件事第一能不能想到逆向思维第二知不知道用优先队列维护贪心过程。1.3 解题方向的抉择正着切还是倒着合我把正向切和逆向合两种思路放到一起对比一下看完你就明白为什么逆向是唯一合理的选择了。正向切入手的难点在于你每次选哪一刀切都会影响后续木板的结构但你又无法判断当前这一步的决策对最终总费用的影响。比如前面那个 21 切成 8、5、8 的例子第一刀切哪里看起来都一样因为费用都是 21但第二刀的费用已经被第一刀的决策锁死了。这说明正向切割的决策会留下很强的“后效性”贪心在这里根本立不住。而逆向合并则完全没有这个问题任意时刻你只需要面对一堆当前存在的木板随便挑两块合并费用清清楚楚地加在总账上。整个过程中未来还剩多少块、怎么合并都不影响当前这一合并的费用计算也不影响已经被合并过的木板的长度属性它们已经变成一块了。这就是典型的无后效性场景贪心策略在这里可以安全使用。所以做这类题第一反应不应该是去模拟题目描述中的操作而是想想有没有一个等价的、更好做的反向过程。这个思维习惯能帮你把一大批“看似复杂”的贪心题瞬间变成模板题。2. 贪心策略的证明与直觉2.1 贪心选最小值的直觉既然问题变成了“每次合并两段木板代价是长度之和”那直觉上就想让那些长度大的木板少参与合并长度小的木板多参与合并。怎么做到哈夫曼已经给出了答案每次选当前最小的两个数合并。为什么因为合并的两个数会“加和”成一个新数继续留在集合里。如果一个数被合并的次数越多它被重复加进总费用的次数就越多。比如长度 1 的小木板如果在合并过程中被合成了 5 次那它的长度 1 就被加了 5 次长度 100 的大木板如果只在最后一次被合并那 100 只被加了一次。自然我们希望大数少相加小数多相加。但“小数多相加”是有限度的你不能为了让 1 多被加几次而故意让合并过程变得低效。每次合并的总费用是两个被合并数之和你把 1 跟一个大数合并这次的费用反而偏高。所以问题变成了一个矛盾小的数要尽量深层参与以减少总费用但每次合并又希望两数尽量小以减少单次费用——Huffman 贪心恰好同时满足这两个目标。2.2 用一张二叉树图看透费用本质把整个合并过程画成一棵二叉树叶子节点是初始的 n 块木板每个内部节点代表一次合并节点权值等于它两个孩子权值之和。那么你付出的总费用恰好等于所有内部节点权值之和。这个结论还有一个更深刻的等价表达总费用等于每个叶子节点的权值乘以它到根节点的路径长度之和。你可以验证一下比如三个叶子 8、5、8如果先合 8513再合 13821总费用 34加权路径和就是 8×2 5×2 8×1 34对上了。所以问题变成了给你一组叶子权值构造一棵二叉树使 Σ(叶子权值 × 深度) 最小。这个问题的经典解法就是 Huffman 算法。它的正确性可以用“局部调整法”证明如果一棵最优二叉树中存在两个深度最大的兄弟叶子那么把它们换成当前最小的两个叶子总代价不会增加。反复应用这个调整最后就得到了每次取两个最小权值合并的构造过程。这里我不展开完整的形式化证明但提一个关键直觉在最优方案中最深的那个叶子一定是当前权值最小的那个否则把更小的权值放到更深的叶子总费用还会下降。同理可证最深的两个兄弟叶子必然对应当前最小的两个权值。于是每一步都取最小的两个就是唯一可能的最优构造。2.3 总结决策规则综合来看这道题的决策规则简单到令人怀疑所有木板长度放进一个小根堆。只要堆里元素个数大于 1就弹出最小的两个数 a、b。把 ab 累加到答案然后把 ab 重新压入堆。重复上面的操作直到堆里只剩一个数。每次弹 a、b 再压回 ab相当于完成了一次合并。为什么要用堆而不直接排序因为合并产生的新的数ab可能比原来某些数大它需要重新找位置插入。每次找最小的两个数用堆的结构可以做到 O(log n)。如果每次都用数组重新排序复杂度会变成 O(n² log n)数据一大直接原地起飞。提示如果题目数据范围很小比如 n ≤ 100你确实可以用每次排序的写法。但洛谷 P1672 的数据范围显然不是让你这么玩的直接用堆才是正确姿势。3. 数据结构选型优先队列的实操要点3.1 为什么必须用堆而不是排序数组有人会问我用一个数组存长度每次 sort 一遍然后取前两个不是也能做吗答案是不能至少在大数据下不能。每次取最小的两个数并合并合并出的新数会破坏数组原本的有序性。继续用排序更新后的数组你需要每次 O(n log n) 排序总共合并 n-1 次总复杂度 O(n² log n)。当 n 到 10^5 级别时这个复杂度大约需要执行 1.7 亿次左右的关键操作在竞赛环境下几乎必然超时。而优先队列二叉堆可以在 O(log n) 时间内找到最小元素并调整结构整体复杂度只有 O(n log n)。同样是 n10^5 的数据跑起来毫秒级。这就是“数据结构选型决定算法复杂度算法复杂度决定是否能 AC”的经典案例。3.2 C 优先队列的使用细节C 标准库里的priority_queue默认是大根堆堆顶是最大元素。要让它变成小根堆堆顶是最小元素有两种办法第一种是传入greaterint比较器#include bits/stdc.h using namespace std; priority_queueint, vectorint, greaterint pq;第二种是往堆里压入负数取出来的时候取反priority_queueint pq; pq.push(-x); // 取出时int cur -pq.top(); pq.pop();第一种写法更直观但需要记住模板的三个参数第二种写法在小根堆的场合也很常用不少老手习惯了这么写。两种都可以我一般推荐第一种因为代码可读性更好。另外注意一个细节如果你需要频繁修改优先队列内部元素比如减少某个值优先队列就不方便了那应该考虑set或multiset。但在 P1672 这种只需要取最小值、插入新值的场景优先队列就是最合适的选择。3.3 复杂度与空间说明时间上每次push和pop都是 O(log n)总共进行 n-1 次合并每次涉及两次 pop、一次 push所以总复杂度 O(n log n)。空间上堆中最多同时存 n 个元素每个元素是一个整数O(n) 的空间完全没问题。值得一提的是priority_queue底层用vector实现默认会有一定的空间冗余但在实际比赛环境中完全不用操心。4. 完整代码实现与细节4.1 C 代码可直接 AC下面是我整理过的 C 实现加了注释方便对照理解#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; // 小根堆存当前所有木板的长度 priority_queuelong long, vectorlong long, greaterlong long pq; for (int i 0; i n; i) { long long x; cin x; pq.push(x); } long long ans 0; // 合并 n-1 次最后堆里只剩一块完整木板 while (pq.size() 1) { long long a pq.top(); pq.pop(); long long b pq.top(); pq.pop(); long long cost a b; ans cost; pq.push(cost); } cout ans \n; return 0; }这段代码几乎是合并果子的标准代码只是变量名换成了木板场景的语义。如果你把合并果子 AC 过这道题往提交框里一放大概率也能直接过。4.2 Python 参考实现Python 没有内置小根堆但heapq默认就是小根堆所以反而更顺手import heapq n int(input()) nums list(map(int, input().split())) heapq.heapify(nums) ans 0 while len(nums) 1: a heapq.heappop(nums) b heapq.heappop(nums) cost a b ans cost heapq.heappush(nums, cost) print(ans)如果你是拿 Python 交题注意输入量大时最好用sys.stdin.buffer.read()一次性读入避免input()一层层慢。另外Python 的整数不会溢出这点比 C 省心。4.3 最容易翻车的三个细节第一个细节是数据类型。题目给出的每块木板长度以及合并后形成的长度都可能很大。更关键的是总费用的增长是“滚雪球”式的每次都要把中间结果再加进答案最后可能超过 32 位整数的范围。所以 C 里答案是long long堆元素类型也用long long别因为输入看似“小数据”就掉以轻心。第二个细节是堆内只剩一个元素时合并循环要结束。这是边界条件很多新手写的循环里没有处理n 1的情况结果弹两次堆导致运行时错误。注意n 1时本来就不需要切割、不需要合并答案就是 0上面的代码天然正确处理因为pq.size() 1为假。第三个细节是输入输出的效率。洛谷的老题数据量虽不至于到夸张的级别但cin不加ios::sync_with_stdio(false)和cin.tie(nullptr)在数据量较大时依然可能差出几十毫秒。竞赛环境下这是一种习惯建议每次写 C 都带上这两行。5. 常见错误与排查技巧实录5.1 错误一正着模拟切割顺序我最初就卡在这。正向模拟需要决策每次切哪一根、从哪个位置下刀还要算每一刀的费用。看似可以用一个“切分树”来做但每次一分成两块会改变后续可切木板的集合这本质上是一个搜索问题不是一个贪心能搞定的。如果你已经写了正向模拟建议先停一下不要想着在正向搜索里剪枝优化。直接转逆向合并代码量直接少一半。这道题能 AC 的写法几乎都是逆向合并。5.2 错误二每次对数组排序而不是用堆有的同学可能会写这样的代码sort(a, an); for (int i 0; i n-1; i) { a[i1] a[i]; ans a[i1]; sort(ai1, an); }思路是每合并一次就把新木板放回数组再排序找当前最小的两块。这个做法在 n 小的时候能过样例但复杂度太差。尤其是你从 i1 开始排序前提是前面的部分已经有序这算是一个小优化但依然不够稳。最稳的做法就是优先队列。5.3 错误三用了大根堆priority_queueint默认大根堆也就是每次取最大元素。如果你忘了加greater合并的就会是最大的两块木板总费用会变成最大。极端情况下答案会大得离谱但样例可能刚好能过——这种“样例过了、提交全 WA”的情况最让人头疼。排查技巧用 n2 的简单数据测试。输入 1 和 100正确答案是 101。如果你输出的不是 101 而是别的第一件事就是检查堆的方向。5.4 错误四把答案算成了最终木板的长度还有一个容易犯的错有人以为总费用等于最终木板的总长度。不对。最终木板长度是固定的等于所有小木板长度之和这部分不随切割顺序变化。但总费用是每次合并费用的加和它包含了中间过程的重复计数所以答案会比最终总长度大等于叶子的加权深度和。如果你觉得答案应该等于 n 块长度之和说明还没理解费用累加的本质。我常用的验证方法自己造一个 n3 的小数据比如 8、5、8手算一遍。第一种合并 5813再加 8总费用 21 等一下这不叫 13821费用是 13 再加 21不对重新算——合并 5 和 8费用 13堆变成 8、13再合并 8 和 13费用 21总费用 132134。最终木板长度也是 21但总费用 34比最终长度大这个差异正好是中间那 13 被重复计入的部分。如果算出来的答案等于所有长度之和说明你的代码没有把所有合并费用都累加大概率是漏了某一步的ans cost。5.5 写在最后的调试建议做贪心题我习惯先写一个暴力 DFS 或枚举所有合并顺序的代码用来对拍小数据。比如枚举 1 到 8随机生成 n8 以内的数组暴力算最小费用再和优先队列贪心的结果对比。对拍上一千组随机数据如果全部一致就可以放心提交了。这道题尤其值得这样做因为 Huffman 贪心虽然正确性有严格证明但初学阶段“凭直觉”很难完全放心。对拍不仅能验证答案还能帮你建立一个很重要的信念贪心算法可以为某些看似复杂的问题提供精确最优解。6. 从 P1672 出发模型识别与扩展6.1 同一模型的不同马甲我在开头说了P1672 和 P1090 合并果子是同一个模型。事实上这种模型在各大 OJ 上遍地都是POJ 3253 Fence Repair几乎就是个换皮题一本通 / OpenJudge 上的“木材加工”“木板切割”类题目一些 ACM 区域赛的签到题也会用这个模型做铺垫这提醒我们一件事算法竞赛里题目的包装千变万化但底层模型是有限的。做题不能只看表面“切木板”“合并果子”“修理围栏”这些题面背后都是一个问题——给一组数每次取两个加起来再放回去求累计和的最小值。你只要把这个模型刻在脑子里再见到任何类似描述都能秒出思路。6.2 扩展如果每次可以合并任意多段有些变体题问的不是“每次合并两段”而是“每次可以合并任意 k 段”。比如合并果子里有个加强版允许每次合并 k 堆果子费用是这 k 堆的重量之和。这时候贪心策略就要改成每次取最小的 k 个数合并。这个算法跟 k 叉 Huffman 编码是对应的。需要注意一个细节如果 (n-1) 不能整除 (k-1)需要在初始序列中补几个 0让最后一次合并凑满 k 个。否则贪心过程会形成一层不满的树答案不是最优。这个点笔试和面试经常考值得留意。6.3 这类“逆向思维”题的识别口诀很多贪心题的共同特征是正向操作存在“后效性”而逆向操作变成无后效性的贪心过程。识别这类题我有一个简单的口诀正向难则逆切变合、拆变并、删变插。比如蓝桥杯的“翻硬币”、洛谷 P1045 麦森数这类题也常常用类似的逆向思维简化问题。以后遇到一个操作让当前状态碎片化、难以局部决策的时候不妨先想想这个操作的逆过程是不是一个简单的贪心或动态规划。就拿我自己来说在卡 P1672 的那段时间我最大的收获不是背会了一个 Huffman 算法而是养成了一种习惯拿到题先问“这个操作反过来是什么样”。这个习惯后来帮我解掉了不少更难的贪心和搜索题。一个经典模型的背后往往藏着一串模型你从模型层面去理解题目刷题效率会高很多。提示如果看到“每个操作的费用 对象的总长度/重量”这种条件基本可以直接锁定 Huffman 合并模型如果看到“每次合并两个求最小总代价”的表述优先队列秒杀。最后再说一句实操层面的小建议洛谷提交时如果 WA先别急着改算法把样例过了之后的隐藏边界测一遍。n1、所有木板长度相同、长度取极大值这三类数据一测你能排掉 90% 的细节错误。剩下 10% 的算法问题用对拍总能揪出来。祝各位刷题顺利AC 到手。
洛谷P1672围栏切割：逆向思维转化为Huffman合并，优先队列贪心解题
洛谷 P1672 这道题光看题面很容易被绕进去——“围栏”、“切割”、“长度”好像就是一道模拟切割过程的题。但刷过类似题的朋友应该已经闻到味了这道题的本质其实是经典的 Huffman 合并问题。和洛谷 P1090 合并果子几乎是一个模子刻出来的区别只在包装方式。我做这道题的时候第一反应也是傻乎乎地去模拟切木板结果样例都过不了。后来把思路反过来想一下就通了。这篇文章就把我的完整推导过程、贪心证明、代码实现和踩坑记录都放出来希望能帮到正在卡这道题的人。1. 题意与核心模型拆解1.1 原题到底在说什么题目说的是有一根长木板长度固定需要切成 n 段每段的长度已经给定了比如要切成 3 段长度分别是 8、5、8。切割有个规矩每次切一刀费用等于当前这块木板的总长度。注意这里不是每切一刀固定收多少钱而是按被切木板本身的长度收费。举个例子一根长度为 21 的木板要切成 8、5、8 三段。如果第一刀把 21 切成 13 和 8费用就是 21。剩下 13 那根再切成 8 和 5费用是 13。总费用 34。但如果第一刀把 21 切成 16 和 5第二刀把 16 切成 8 和 8总费用就是 21 16 37。同样的三段切割顺序不同花的钱就不一样。题目让你求最小总费用。很多人第一眼看到这个题会以为要动态规划毕竟是个最优化问题。但其实这题有个非常漂亮的转化把“切”反过来看变成“拼”。既然切木板是长木板一分为二那反过来就是把若干小木板一段一段拼回那根长木板。每次拼两段费用等于这两段长度之和。这样问题就变成了有 n 个长度已知的小木板每次任选两块拼在一起代价是这两块的长度之和问把 n 块合成一整块木板的最小总代价。这个转化很关键因为它把一个“未知目标拆成已知片段”的优化问题变成了“把已知片段合并成整体”的合并问题。1.2 为什么“切木板”和“合并果子”是同一道题做过 P1090 合并果子的人应该已经看出来了这就是同一道题。合并果子的题意是有 n 堆果子每次合并两堆代价是两堆重量之和求最小总代价。这跟“把 n 段木板拼起来”在数学上完全等价连数据范围都懒得换。我当时就是被“切割”这两个字误导了在“正着切”的路上越走越远。实际上正着切你很难找到一个好的贪心策略因为每次切哪里会改变之后所有块的大小而且你也不知道哪一刀是“赚”的。但是倒着拼问题就清晰多了每次合并的两段木板它们各自在后续的每次合并中都会被继续计入费用所以长度越短的木板越应该被“深藏”在合并过程的下层越晚参与那些产生大费用的合并。这也是 Huffman 编码的核心思想让权值小的叶子拥有更长的路径权值大的叶子拥有更短的路径从而让整棵树的加权路径长度最小。所以这道题其实考两件事第一能不能想到逆向思维第二知不知道用优先队列维护贪心过程。1.3 解题方向的抉择正着切还是倒着合我把正向切和逆向合两种思路放到一起对比一下看完你就明白为什么逆向是唯一合理的选择了。正向切入手的难点在于你每次选哪一刀切都会影响后续木板的结构但你又无法判断当前这一步的决策对最终总费用的影响。比如前面那个 21 切成 8、5、8 的例子第一刀切哪里看起来都一样因为费用都是 21但第二刀的费用已经被第一刀的决策锁死了。这说明正向切割的决策会留下很强的“后效性”贪心在这里根本立不住。而逆向合并则完全没有这个问题任意时刻你只需要面对一堆当前存在的木板随便挑两块合并费用清清楚楚地加在总账上。整个过程中未来还剩多少块、怎么合并都不影响当前这一合并的费用计算也不影响已经被合并过的木板的长度属性它们已经变成一块了。这就是典型的无后效性场景贪心策略在这里可以安全使用。所以做这类题第一反应不应该是去模拟题目描述中的操作而是想想有没有一个等价的、更好做的反向过程。这个思维习惯能帮你把一大批“看似复杂”的贪心题瞬间变成模板题。2. 贪心策略的证明与直觉2.1 贪心选最小值的直觉既然问题变成了“每次合并两段木板代价是长度之和”那直觉上就想让那些长度大的木板少参与合并长度小的木板多参与合并。怎么做到哈夫曼已经给出了答案每次选当前最小的两个数合并。为什么因为合并的两个数会“加和”成一个新数继续留在集合里。如果一个数被合并的次数越多它被重复加进总费用的次数就越多。比如长度 1 的小木板如果在合并过程中被合成了 5 次那它的长度 1 就被加了 5 次长度 100 的大木板如果只在最后一次被合并那 100 只被加了一次。自然我们希望大数少相加小数多相加。但“小数多相加”是有限度的你不能为了让 1 多被加几次而故意让合并过程变得低效。每次合并的总费用是两个被合并数之和你把 1 跟一个大数合并这次的费用反而偏高。所以问题变成了一个矛盾小的数要尽量深层参与以减少总费用但每次合并又希望两数尽量小以减少单次费用——Huffman 贪心恰好同时满足这两个目标。2.2 用一张二叉树图看透费用本质把整个合并过程画成一棵二叉树叶子节点是初始的 n 块木板每个内部节点代表一次合并节点权值等于它两个孩子权值之和。那么你付出的总费用恰好等于所有内部节点权值之和。这个结论还有一个更深刻的等价表达总费用等于每个叶子节点的权值乘以它到根节点的路径长度之和。你可以验证一下比如三个叶子 8、5、8如果先合 8513再合 13821总费用 34加权路径和就是 8×2 5×2 8×1 34对上了。所以问题变成了给你一组叶子权值构造一棵二叉树使 Σ(叶子权值 × 深度) 最小。这个问题的经典解法就是 Huffman 算法。它的正确性可以用“局部调整法”证明如果一棵最优二叉树中存在两个深度最大的兄弟叶子那么把它们换成当前最小的两个叶子总代价不会增加。反复应用这个调整最后就得到了每次取两个最小权值合并的构造过程。这里我不展开完整的形式化证明但提一个关键直觉在最优方案中最深的那个叶子一定是当前权值最小的那个否则把更小的权值放到更深的叶子总费用还会下降。同理可证最深的两个兄弟叶子必然对应当前最小的两个权值。于是每一步都取最小的两个就是唯一可能的最优构造。2.3 总结决策规则综合来看这道题的决策规则简单到令人怀疑所有木板长度放进一个小根堆。只要堆里元素个数大于 1就弹出最小的两个数 a、b。把 ab 累加到答案然后把 ab 重新压入堆。重复上面的操作直到堆里只剩一个数。每次弹 a、b 再压回 ab相当于完成了一次合并。为什么要用堆而不直接排序因为合并产生的新的数ab可能比原来某些数大它需要重新找位置插入。每次找最小的两个数用堆的结构可以做到 O(log n)。如果每次都用数组重新排序复杂度会变成 O(n² log n)数据一大直接原地起飞。提示如果题目数据范围很小比如 n ≤ 100你确实可以用每次排序的写法。但洛谷 P1672 的数据范围显然不是让你这么玩的直接用堆才是正确姿势。3. 数据结构选型优先队列的实操要点3.1 为什么必须用堆而不是排序数组有人会问我用一个数组存长度每次 sort 一遍然后取前两个不是也能做吗答案是不能至少在大数据下不能。每次取最小的两个数并合并合并出的新数会破坏数组原本的有序性。继续用排序更新后的数组你需要每次 O(n log n) 排序总共合并 n-1 次总复杂度 O(n² log n)。当 n 到 10^5 级别时这个复杂度大约需要执行 1.7 亿次左右的关键操作在竞赛环境下几乎必然超时。而优先队列二叉堆可以在 O(log n) 时间内找到最小元素并调整结构整体复杂度只有 O(n log n)。同样是 n10^5 的数据跑起来毫秒级。这就是“数据结构选型决定算法复杂度算法复杂度决定是否能 AC”的经典案例。3.2 C 优先队列的使用细节C 标准库里的priority_queue默认是大根堆堆顶是最大元素。要让它变成小根堆堆顶是最小元素有两种办法第一种是传入greaterint比较器#include bits/stdc.h using namespace std; priority_queueint, vectorint, greaterint pq;第二种是往堆里压入负数取出来的时候取反priority_queueint pq; pq.push(-x); // 取出时int cur -pq.top(); pq.pop();第一种写法更直观但需要记住模板的三个参数第二种写法在小根堆的场合也很常用不少老手习惯了这么写。两种都可以我一般推荐第一种因为代码可读性更好。另外注意一个细节如果你需要频繁修改优先队列内部元素比如减少某个值优先队列就不方便了那应该考虑set或multiset。但在 P1672 这种只需要取最小值、插入新值的场景优先队列就是最合适的选择。3.3 复杂度与空间说明时间上每次push和pop都是 O(log n)总共进行 n-1 次合并每次涉及两次 pop、一次 push所以总复杂度 O(n log n)。空间上堆中最多同时存 n 个元素每个元素是一个整数O(n) 的空间完全没问题。值得一提的是priority_queue底层用vector实现默认会有一定的空间冗余但在实际比赛环境中完全不用操心。4. 完整代码实现与细节4.1 C 代码可直接 AC下面是我整理过的 C 实现加了注释方便对照理解#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; // 小根堆存当前所有木板的长度 priority_queuelong long, vectorlong long, greaterlong long pq; for (int i 0; i n; i) { long long x; cin x; pq.push(x); } long long ans 0; // 合并 n-1 次最后堆里只剩一块完整木板 while (pq.size() 1) { long long a pq.top(); pq.pop(); long long b pq.top(); pq.pop(); long long cost a b; ans cost; pq.push(cost); } cout ans \n; return 0; }这段代码几乎是合并果子的标准代码只是变量名换成了木板场景的语义。如果你把合并果子 AC 过这道题往提交框里一放大概率也能直接过。4.2 Python 参考实现Python 没有内置小根堆但heapq默认就是小根堆所以反而更顺手import heapq n int(input()) nums list(map(int, input().split())) heapq.heapify(nums) ans 0 while len(nums) 1: a heapq.heappop(nums) b heapq.heappop(nums) cost a b ans cost heapq.heappush(nums, cost) print(ans)如果你是拿 Python 交题注意输入量大时最好用sys.stdin.buffer.read()一次性读入避免input()一层层慢。另外Python 的整数不会溢出这点比 C 省心。4.3 最容易翻车的三个细节第一个细节是数据类型。题目给出的每块木板长度以及合并后形成的长度都可能很大。更关键的是总费用的增长是“滚雪球”式的每次都要把中间结果再加进答案最后可能超过 32 位整数的范围。所以 C 里答案是long long堆元素类型也用long long别因为输入看似“小数据”就掉以轻心。第二个细节是堆内只剩一个元素时合并循环要结束。这是边界条件很多新手写的循环里没有处理n 1的情况结果弹两次堆导致运行时错误。注意n 1时本来就不需要切割、不需要合并答案就是 0上面的代码天然正确处理因为pq.size() 1为假。第三个细节是输入输出的效率。洛谷的老题数据量虽不至于到夸张的级别但cin不加ios::sync_with_stdio(false)和cin.tie(nullptr)在数据量较大时依然可能差出几十毫秒。竞赛环境下这是一种习惯建议每次写 C 都带上这两行。5. 常见错误与排查技巧实录5.1 错误一正着模拟切割顺序我最初就卡在这。正向模拟需要决策每次切哪一根、从哪个位置下刀还要算每一刀的费用。看似可以用一个“切分树”来做但每次一分成两块会改变后续可切木板的集合这本质上是一个搜索问题不是一个贪心能搞定的。如果你已经写了正向模拟建议先停一下不要想着在正向搜索里剪枝优化。直接转逆向合并代码量直接少一半。这道题能 AC 的写法几乎都是逆向合并。5.2 错误二每次对数组排序而不是用堆有的同学可能会写这样的代码sort(a, an); for (int i 0; i n-1; i) { a[i1] a[i]; ans a[i1]; sort(ai1, an); }思路是每合并一次就把新木板放回数组再排序找当前最小的两块。这个做法在 n 小的时候能过样例但复杂度太差。尤其是你从 i1 开始排序前提是前面的部分已经有序这算是一个小优化但依然不够稳。最稳的做法就是优先队列。5.3 错误三用了大根堆priority_queueint默认大根堆也就是每次取最大元素。如果你忘了加greater合并的就会是最大的两块木板总费用会变成最大。极端情况下答案会大得离谱但样例可能刚好能过——这种“样例过了、提交全 WA”的情况最让人头疼。排查技巧用 n2 的简单数据测试。输入 1 和 100正确答案是 101。如果你输出的不是 101 而是别的第一件事就是检查堆的方向。5.4 错误四把答案算成了最终木板的长度还有一个容易犯的错有人以为总费用等于最终木板的总长度。不对。最终木板长度是固定的等于所有小木板长度之和这部分不随切割顺序变化。但总费用是每次合并费用的加和它包含了中间过程的重复计数所以答案会比最终总长度大等于叶子的加权深度和。如果你觉得答案应该等于 n 块长度之和说明还没理解费用累加的本质。我常用的验证方法自己造一个 n3 的小数据比如 8、5、8手算一遍。第一种合并 5813再加 8总费用 21 等一下这不叫 13821费用是 13 再加 21不对重新算——合并 5 和 8费用 13堆变成 8、13再合并 8 和 13费用 21总费用 132134。最终木板长度也是 21但总费用 34比最终长度大这个差异正好是中间那 13 被重复计入的部分。如果算出来的答案等于所有长度之和说明你的代码没有把所有合并费用都累加大概率是漏了某一步的ans cost。5.5 写在最后的调试建议做贪心题我习惯先写一个暴力 DFS 或枚举所有合并顺序的代码用来对拍小数据。比如枚举 1 到 8随机生成 n8 以内的数组暴力算最小费用再和优先队列贪心的结果对比。对拍上一千组随机数据如果全部一致就可以放心提交了。这道题尤其值得这样做因为 Huffman 贪心虽然正确性有严格证明但初学阶段“凭直觉”很难完全放心。对拍不仅能验证答案还能帮你建立一个很重要的信念贪心算法可以为某些看似复杂的问题提供精确最优解。6. 从 P1672 出发模型识别与扩展6.1 同一模型的不同马甲我在开头说了P1672 和 P1090 合并果子是同一个模型。事实上这种模型在各大 OJ 上遍地都是POJ 3253 Fence Repair几乎就是个换皮题一本通 / OpenJudge 上的“木材加工”“木板切割”类题目一些 ACM 区域赛的签到题也会用这个模型做铺垫这提醒我们一件事算法竞赛里题目的包装千变万化但底层模型是有限的。做题不能只看表面“切木板”“合并果子”“修理围栏”这些题面背后都是一个问题——给一组数每次取两个加起来再放回去求累计和的最小值。你只要把这个模型刻在脑子里再见到任何类似描述都能秒出思路。6.2 扩展如果每次可以合并任意多段有些变体题问的不是“每次合并两段”而是“每次可以合并任意 k 段”。比如合并果子里有个加强版允许每次合并 k 堆果子费用是这 k 堆的重量之和。这时候贪心策略就要改成每次取最小的 k 个数合并。这个算法跟 k 叉 Huffman 编码是对应的。需要注意一个细节如果 (n-1) 不能整除 (k-1)需要在初始序列中补几个 0让最后一次合并凑满 k 个。否则贪心过程会形成一层不满的树答案不是最优。这个点笔试和面试经常考值得留意。6.3 这类“逆向思维”题的识别口诀很多贪心题的共同特征是正向操作存在“后效性”而逆向操作变成无后效性的贪心过程。识别这类题我有一个简单的口诀正向难则逆切变合、拆变并、删变插。比如蓝桥杯的“翻硬币”、洛谷 P1045 麦森数这类题也常常用类似的逆向思维简化问题。以后遇到一个操作让当前状态碎片化、难以局部决策的时候不妨先想想这个操作的逆过程是不是一个简单的贪心或动态规划。就拿我自己来说在卡 P1672 的那段时间我最大的收获不是背会了一个 Huffman 算法而是养成了一种习惯拿到题先问“这个操作反过来是什么样”。这个习惯后来帮我解掉了不少更难的贪心和搜索题。一个经典模型的背后往往藏着一串模型你从模型层面去理解题目刷题效率会高很多。提示如果看到“每个操作的费用 对象的总长度/重量”这种条件基本可以直接锁定 Huffman 合并模型如果看到“每次合并两个求最小总代价”的表述优先队列秒杀。最后再说一句实操层面的小建议洛谷提交时如果 WA先别急着改算法把样例过了之后的隐藏边界测一遍。n1、所有木板长度相同、长度取极大值这三类数据一测你能排掉 90% 的细节错误。剩下 10% 的算法问题用对拍总能揪出来。祝各位刷题顺利AC 到手。
