前阵子刷洛谷的题单翻到 P7871「Wdoi-4」芙兰姆Q贤者与谜题难度标着普及。说实话第一眼看到这个标题我是有点想笑的芙兰姆Q这种自带吐槽气质的名字加上贤者与谜题的组合给人的感觉就像一道专门来调戏人的脑筋急转弯。但仔细做了几分钟之后发现这其实是一道非常典型的贪心 差分数组结合题难度定在普及恰到好处——它不会像纯模板题那样无脑套板子但也没有难到要上高级数据结构重点考察的是你能否从题目描述中抽象出正确的模型并且想清楚贪心策略为什么是对的。这篇文章我就以这道题为引子把这类区间修改 贪心统计题目的完整思考链路拆开来讲。里面会涉及差分数组的本质理解、贪心策略如何从目标序列反推出来、以及我在实际调试中踩过的几个小坑。不论你是刚开始刷普及组题目还是已经进入提高组准备阶段这套看见区间操作想差分、看见求最小次数想贪心的思路都是能直接迁移到很多题目上的。后面我会先讲整体思路是怎么从题目里抽出来的再讲差分数组的底层原理和实操细节接着是贪心推导和参考代码最后做一些常见问题和调试经验整理尽量让你看完就能独立写出可行的解法。1. 先被题目名字骗了谜题外壳下是经典的区间操作模型很多刷题的人有个不太好的习惯看到题目名很搞笑、题面很长、背景故事花里胡哨就下意识觉得题目很难。但实际这类剧情包装型题目往往内部逻辑反而更朴素——出题人把算法藏在一个充满人设和世界观的故事里考验的正是你把非结构化文本翻译成结构化算法的能力。P7871 就属于这种情况题目再怎么芙兰姆Q剥开外壳之后核心就是一个关于区间操作的最优化问题。1.1 把谜题翻译成算法语言我做题的第一步永远是去包装。不管题面讲了什么贤者、魔法书、谜题还是谜之少女最终能被计算机处理的只能是一组数字、若干操作和一个目标函数。这道题给出的大致模型是你有一个初始状态需要通过一系列区间操作把某个序列变成题目要求的目标序列同时希望操作次数或者某种代价最小。一旦进入这个抽象层面你会发现它和很多熟悉的题目长得非常像。比如经典的积木大赛、NOIP 2013 的积木搭建、还有各种刷栅栏填坑类型的题骨子里都是同一套东西给定最终要达成的序列每次操作可以选择一个连续区间对区间整体执行某个动作求最小操作数。关键点在于题目往往不会直接告诉你这是区间加减问题而是通过故事把操作藏在描述里。你需要在阅读时主动识别关键词连续的一段、同时变化、每次选择区间……这一类的暗示基本都指向区间操作。识别出这一点后续的思考方向就被锁定了区间操作的话要么用线段树之类的数据结构去模拟要么用差分数组去转换操作形式。1.2 为什么是差分数组而不是线段树看到区间加的时候很多人的第一反应是线段树、树状数组这类支持区间修改、区间查询的数据结构。这种直觉没有错在某些问题里线段树确实是最优解。但请注意如果题目只要求最终结果是一个统计量比如最小操作次数而不要求在线维护区间值那上线段树基本是杀鸡用牛刀写起来还容易出错。差分数组就完全是另一个思路它不直接维护原序列而是维护原序列的变化趋势。你可以把差分数组想象成放大镜下的序列形态突变点。原序列的区间加法在差分数组里会被降维成两个端点的修改。也就是说原本区间操作需要 O(n) 的修改量用差分后变成 O(1) 的端点修改。这是个极其重要的思维跃迁区间操作不再是一个必须遍历整段的事情而是只关心边界的事情。当你的贪心策略只需要基于边界处的增量来做判断时差分数组就成了最合适的数据结构。我在做这道题时没有碰任何重量级数据结构全程就维护了一个差分数组代码量很小运行复杂度是 O(n)这才是普及难度题应有的优雅感。1.3 贪心在这里的意义按照我的经验凡是要求最小操作次数的区间操作题十有八九要跟贪心挂钩。原因是这类问题往往具备局部最优能推出全局最优的性质。但能贪心不是天上掉下来的你需要先找到一种排序、一种统计规则使得每一步的选择都不会让后续变得更差。在 P7871 这个模型里贪心的对象不是某个具体的操作序列而是如何让一次操作产生尽可能多的收益。更直白一点说如果我每次操作都尽量让当前最缺的位置得到满足那累计的操作次数就是最优的。这种每次把最高优先级的需求处理掉的直觉正是贪心算法的灵魂。不过光有直觉还不够我们需要一个严谨的模型来支撑这样贪是对的。下面我就从差分数组的原理讲起逐步推导出这个贪心规则到底是什么。2. 差分数组把区间操作变成端点变化的艺术既然决定了要用差分数组那就必须把它彻底吃透。很多人的问题是会用但是不懂一遇到变形题就抓瞎。我在这道题上恰恰是利用了对差分数组本质的理解来快速锁定解法所以这一节我把它的定义、还原、以及和区间操作的关系掰开揉碎讲清楚。2.1 差分数组的定义与还原假设我们有一个原始序列 a长度是 n下标从 1 到 n。它的差分数组 d 定义为d[1] a[1]d[i] a[i] - a[i-1]其中 2 ≤ i ≤ n也可以更严格地定义 d[n1] -a[n]方便处理末尾的跃迁。这样定义之后原数组 a 其实就是差分数组 d 的前缀和a[i] d[1] d[2] ... d[i]这里我强烈建议你亲自算一组小数据。比如 a [2, 2, 4, 4, 4]那 d [2, 0, 2, 0, 0, -4]最后一项是 a[n] 的相反数加进来的目的是让差分数组总和为 0。再看一次前缀和你会发现每一轮累加都能还原出 a 的每个元素。对这个对应关系越熟后面看问题就越快。为什么要给自己加 d[n1] 这个多余的项原因很实用差分数组中每个正值最终都要对应一个负值二者数量相等才能把整个序列还原成有限高度。计算差分数组的总和时如果你漏掉最后那一项会得到 a[n] 而不是 0这个 bug 在贪心计数时会非常隐蔽。我后面讲常见问题时会再次提到这一点。2.2 区间加法在差分视角下的表现现在来看核心性质如果我想把 a[l] 到 a[r] 这一整段都加上 v直接操作用循环需要 r - l 1 次改动。但放到差分数组里看区间内所有相邻元素的差值都不会变变化的只有两个位置d[l] 增加 vd[r1] 减少 v这就是区间操作 - 端点变化的全部秘密。打个生活比方假设差分数组是一条马路的路面高度变化记录表区间整体加 v 就像在 l 处放了一块挡板让水位上升 v然后在 r1 处开一个口把水位降回原来的水平。真正发生变化的就是挡板处和开口处中间路段只是继承了这个高度变化而已。这个视角给我们的启发巨大原本我们觉得长度不同的区间是不同量级的操作但在差分视角下任何区间操作都简化为选两个端点一正一负。因此设计操作方案本质上就是不断选择两个端点让差分数组里冒出来的正值和负值互相抵消。抵消的方式不同对应的区间长度就不同也就是说区间操作次数的优化等价于正负端点配对方式的优化。2.3 构造目标变成消去差分拿到题目目标序列的时候我是先求出目标序列的差分数组然后暂停一下问自己如果初始状态是全 0那我要做多少区间加操作才能到达这个差分状态这里可以逆向思维从全 0 构造目标序列等价于把一个全 0 的差分数组升级成目标差分数组。而每次区间加 v正好是在两个端点上制造 v 和 -v。如果你允许 v 是任意正整数那问题就变成用若干个positive 和一个-negative的对子去凑出目标差分数组。要最少操作次数自然希望每个操作都尽量大也就是尽量一次配对消掉尽量多的需求。如果你想要更严格的模型可以这样想定义一个 d[1..n1] 为目标序列的差分。差分数组所有正值的和是 S所有负值的绝对值之和也是 S因为总和为 0。任何一次区间加操作最多让 S 减少 v 的贡献。如果每次操作都恰好把某个正值位的全部需求量和一个负值位的全部容纳量同时消掉那就用掉了最小数量的操作。而这个操作次数恰好就是差分数组正值之和或负值绝对值之和。这不是巧合是正负守恒的必然结果。3. 贪心策略的完整推导与代码落地这节我讲我自己做题时的推演路径以及最终落地的参考代码。很多题解直接把答案是差分数组正数之和甩出来就完事了但这会让读者完全理解不了为什么遇到变体题就卡住。所以这里我会先讲 为什么要这样计数 的直觉再给出正确性思路最后放一段可直接运行的 C 参考实现。3.1 从目标序列反推操作方案我在草稿纸上模拟的过程大概是这样的。假设目标序列 a [4, 1, 4, 2, 3]先逐步观察想象你手里有一把区间刷子每次可以把一段连续区域整体抬高 1。你要从全 0 刷出这个形状。最直观的想法是先看最左边的高度 4必然有 4 次操作从第 1 格开始再看第 2 格只有 1那其中只有 1 次操作能延续到这里说明有 3 次操作在第 1 格和第 2 格之间必须收尾再看第 3 格高度又涨到 4比第 2 格多了 3说明又有 3 次操作在这里重新开始…… 把每次涨上去的差值加在一起就是总的开始次数也就是总操作数。这个过程用语言描述非常啰嗦但如果你把差分数组算出来一切就清清楚楚了。还是以 a [4, 1, 4, 2, 3] 为例差分数组是d [4, -3, 3, -2, 1, -3]正的差值4、3、1就表示这里必须有新操作开始而且每上涨 1 个单位就对应一次新的刷子行程。总操作次数 4 3 1 8。这个 8 也恰好等于负值绝对值之和3 2 3 8因为每次都有一段刷子行程必须收尾。这个守恒关系非常漂亮。3.2 贪心规则与正确性理解为什么可以保证这个贪心计数是最优的我们把问题看作用区间覆盖需求曲线每次覆盖必须是一个连续区间。贪心策略本质上是每次操作都尽可能长地延伸一直延伸到自己高度不够为止。也就是说当前格需要 4 层我就先开 4 条刷子行程下一格只需要 1 层那我就必须立刻关闭 3 条行程下一格又需要 4 层我又新开 3 条行程……这种需要就开、不需要就关的做法完全不浪费任何一次行程的覆盖能力。可能有人会问为什么不把上一格的行程跨过高度低的那一格直接刷到后面的高处可以但你要明白每刷一个中途的低矮区都是白刷——这些操作对这个区域是无效的、甚至是违反最终要求的因为目标那里没有这么高。所以任何合法的操作方案都不会跨越那些比自己当前高度低的区域去覆盖别处。这就在逻辑上锁死了操作区间一个行程从哪里开始必然在它遇到的第一个高度低于自己的位置结束。这个就地启停的规则没有任何浪费因此就是最优。更形式化的讲法是用最短区间覆盖和差分守恒来论证设差分数组正数之和为 S任意一次操作至多让 S 减少 v等于区间左端点差分的正值部分全部消掉时达到上限。要构造目标需要把 S 全部消掉所以操作次数 ≥ S而每次遇到正值就开、遇到负值就关的贪心策略恰好用 S 次操作做到了这一点所以它是最优解。3.3 核心代码实现参考基于上述推导代码其实非常短。我给出一个标准 C 实现#include bits/stdc.h using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorll a(n 2, 0), d(n 2, 0); for (int i 1; i n; i) { cin a[i]; } // 构建差分数组下标 1 到 n1 for (int i 1; i n 1; i) { d[i] a[i] - a[i - 1]; } ll ans 0; for (int i 1; i n 1; i) { if (d[i] 0) { ans d[i]; } } cout ans \n; return 0; }这个代码有几个关键点。第一是 a 和 d 都开到了 n2并且 a[n1] 默认为 0这样构建差分数组时 d[n1] 0 - a[n]自动成为最后一个收尾负值。第二是使用 long long因为目标值范围如果很大差分累积量可能超过 int 上限这点我后面单独说。第三是整个复杂度只有 O(n)扫一遍差分正数求和完事。拿到这个参考代码你完全可以照着跑一遍示例数据验证答案。但我的建议是不要止步于AC 了你可以自己构造几个极端数据比如全递增、全递减、所有元素相等、单峰形状等用手算验证代码输出这会极大帮助你建立起差分 贪心的直觉。4. 实际调试中踩过的坑与速判技巧就算理清了算法写代码的时候还是有一些细节容易出错。这一节我整理了几个我在练习和帮别人 review 代码时经常遇到的坑以及一套快速判断这题能不能用差分数组 贪心的方法。4.1 差分还原时漏掉 n1 这个幽灵项如果你没有把差分数组定义到 d[n1]而是只定义到 d[n]那么你在做正数求和的时候会少算最后一段本应开启的操作。举个例子单调递增序列 [1, 2, 3, 4, 5]差分是 [1, 1, 1, 1, 1]但如果你在 n5 处结束正数之和是 5看起来好像没问题这其实是运气好。换成 [5, 4, 3, 2, 1]差分是 [5, -1, -1, -1, -1]正数之和是 5答案应该是 5依然没问题。问题出在哪里呢再想一个例子[0, 0, 0]显然答案是 0差分 d [0, 0, 0]没问题。但真实的问题常出在统计思路不统一的时候如果你只用 d[i] a[i] - a[i-1]i 从 1 到 n并且只累加正值答案也是对的因为操作次数等于正数之和本来就不依赖负值收尾。危险的是当你试图用负值绝对值之和或者最大值法去验证答案时漏掉 d[n1] -a[n] 就会导致负值之和少了 a[n]让你误以为算错了或者题目有坑。所以我强烈建议你们从第一步构建差分就写到 n1。这是一个习惯问题确定好 d[n1] 的位置以后所有关于守恒的推导都能自洽排查问题也容易得多。4.2 贪心方向搞反是看上升过程不是看绝对值我也见过一些朋友把这题做成求最大值或者求总和原因就是没有抓住从 0 开始上涨才需要新操作这个核心。比如数组是 [100, 1, 100]你觉得答案是 101 吗不对正确答案是 199也不是。我们用差分d [100, -99, 99, -100]含 n1 项正值之和是 199所以答案是 199。你看它既不是最大值 100也不是总和 201而是把所有上升量加起来。这个反直觉点非常关键一段区间只要保持高度不降是可以通过之前的操作延续覆盖的不会产生新的操作成本一旦高度下降说明某些操作在这里必须结束一旦高度再次上升就需要重新开始新操作。所以真正产生成本的是每一个正差分值而不是每个格子的高度。我这里再建议你手动画一条折线图把每个拐点标出来你会发现答案刚好是折线所有上升段的高度之和这个几何直觉比硬背公式有用得多。4.3 数据范围与类型溢出普及的题目所给的数据范围往往比入门题刁钻不少。如果 n 可以到 10^6而 a[i] 可以到 10^9那么差分数组的正数之和在最坏情况下序列递增就是 n 乘以跨度可能轻松突破 10^12。用 int 保存答案LE 是必然的。我自己的习惯是见计算目标涉及累加、累乘的场景一律开 long long哪怕题目数据看起来不大。因为 long long 在 64 位系统上代价很低但溢出 bug 的调试成本极高。如果你是在洛谷这种在线评测环境溢出不会报 RE直接 WA 或者莫名 TLE 都可能非常折磨人。另外要注意差分数组本身也可能包含负数如果你用 unsigned long long 去存那就彻底翻车了。使用 signed 类型并且在累加正数时先判断 d[i] 0这个顺序别搞反。有些人喜欢先取绝对值再累加这在这个模型里并不是好习惯因为我们要区分正负、开和关两者语义不同。4.4 快速识别差分 贪心题型的三个特征最后分享一个我觉得特别实用的经验见到新题时可以按这三条快速判断方向特征说明操作是区间整体增减题目中出现一段连续的区间同时 1/-1或等价描述目标是一个确定序列输入给定最终要达成的序列不是在线动态修改求最值/最小次数常见问法是最少操作多少次、最少需要几个区间只要三条同时命中基本就可以进入差分数组 贪心的推导流程。如果只有前两条也可能是线段树、树状数组维护的题。第三条一出现优先级就变了先想差分的转换再想贪心的规则大概率能走通。我还想多嘴一句P7871 这题本身名字看着像搞笑题但它设计的考点其实非常正统。像差分数组 贪心计数这种组合在区域赛和省选级别的题目里也经常作为前驱模型出现。一次把这种题目吃透后面看到区间加 最小化操作的变体比如限制每个操作长度、限制端点位置、或者操作的值是负数你都能在原有模型上做小步调整。5. 写在最后的个人做题体会我自己在刷这题时最大的感受是一道题能不能快速做出来往往不在于会不会某个算法而在于能不能从一段充满干扰描述的文字里抓住区间和最值这两个信号。差分数组不是什么高深东西但它的转换能力真的会让很多看似复杂的问题变成一遍扫描。当你体会到区间操作被化简成两个端点的改动时你会理解为什么那么多题解都反复强调差分数组——因为它不只是算法更是一种观察序列的方式。最后再分享一个我个人的调试小技巧遇到这种题别急着写代码先在草稿纸上画一条目标序列的折线图然后把所有上升沿标出来。记住上升沿的高度总和就是答案。这个几何直觉可以在你做任何变体题时快速帮你预估答案也能帮你在对拍调试时一眼发现哪里算错了。很多时候我debug代码就是靠这个画线法手工验算几组数据比瞪着屏幕找逻辑错误快得多。