看到 P7871 的标签是“贪心、差分数组”难度普及熟练的选手心里其实已经有了一个大致剧本把问题里的区间操作翻译成差分数组上的端点事件再用贪心把事件配对收尾。题目名字起得花哨带着东方系列那套“芙兰、姆Q、贤者”的谜题风味但算法内核并不玄乎——这类题考的就是你有没有把“区间修改”和“最少操作次数”这两个关键词第一时间接进“差分数组 贪心扫描”的框架里。这篇东西我打算照着自己在洛谷上的做题习惯来写先讲清楚拿到题该怎么拆再讲贪心为什么在这里是对的最后给一套能直接套用的代码模板顺带把反悔贪心的进阶玩法也说透。适合刚学完差分数组、正在往普及难度进阶的选手也适合那些“题解看得懂、自己做就卡壳”的朋友。1. 拿到题先别急着写把“区间操作”翻译成“差分事件”1.1 差分数组为什么能压缩区间操作先复习一个老生常谈但极其关键的定义。设原数组为a[1..n]为了方便通常补一个a[0] 0差分数组定义为d[i] a[i] - a[i-1]反过来原数组可以通过前缀和还原a[i] d[1] d[2] ... d[i]这个定义本身很简单但真正值钱的是下面这个对应关系对原数组执行“区间[l, r]整体加 1”等价于在差分数组上做两个单点修改d[l] 1d[r1] - 1。为什么因为区间内部相邻元素的差值没有变化只有区间的左边界和右边界外侧的差值改变了。你可以把差分数组想象成一本只记录“变化量”的账本每次转账不需要改动整条流水只需要在转出方和转入方各记一笔。同理区间加这种全局耦合的操作在差分视角下被拆成了两个完全独立的事件。这个视角很重要因为“区间操作”往往是一次影响一大片暴力维护的复杂度是 O(n) 甚至更高而差分把一次操作压成了 O(1) 的两个点修改。更重要的是它把“原数组要满足什么条件”这种全局约束变成了“差分数组上若干个点的约束”。比如“所有元素相等”这个条件翻译到差分就是d[2..n]全部为 0而“原数组非负”则等价于差分数组的任意前缀和都非负。很多东西一下子从“看不清全局”变成了“只扫一遍就能判断”。1.2 目标约束怎么落到差分上做题的第一步永远是先把题面里的目标翻译成数学表达。假设题目要你把初始数组start变成目标数组target那我们关心的其实是一个差值数组b[i] target[i] - start[i]也就是说所有操作都是在给这个“缺了多少”的数组做叠加。对这个差值数组再求一次差分得到db[i] b[i] - b[i-1]那么问题就变成了“初始时b全为 0每次操作可以给b的某个区间整体加 1问最少多少次能让b变成目标差值数组。”来一个具体的例子方便后面推导。假设要从全 0 数组变成target [1, 2, 2, 1, 0]它的差分数组是db[1] 1 db[2] 1 db[3] 0 db[4] -1 db[5] -1 db[6] 0 // 哨兵位置n1正差分之和是1 1 2。手算一下也确实只需要两次操作第一次给[1, 4]整体加 1第二次给[2, 3]整体加 1就得到了[1, 2, 2, 1, 0]。两次操作对应的正是两个正差分。这个例子的结论我会在下一节给出严格解释你先有个直觉正差分看起来就是“不得不新开操作的地方”。实际做这类题的时候我建议在草稿纸上先把db写出来然后问自己三个问题正差分能不能对应到一次操作的左端点负差分能不能对应到右端点这些端点之间的配对有没有额外限制如果题面没有额外限制那恭喜你这道题已经完成 80% 了。2. 贪心的出现不是玄学是“区间开闭”问题的最优性2.1 每次操作的本质开一个区间关一个区间很多人记结论只记一句“答案等于正差分之和”但不知道为什么。如果只是背结论遇到题目稍加变形就会卡住。下面我用一个更直观的模型推导一遍。把一次区间加操作看成“打开一个区间然后稍后关闭它”。从左往右扫描差分数组遇到正差分db[i] x意味着这里需要“新开”x个区间因为差分突然升高了必须有这么多个区间的左端点落在位置i。遇到负差分db[i] -y意味着这里需要“关闭”y个区间因为差分突然降低了必须有这么多个区间的右端点落在位置i-1对应差分数组的位置i减 1。整个过程就像拿手头的积木搭一座山上升的时候必须新拿积木往上叠下降的时候把手头还没用完的积木撤掉。你手里同时持有的积木数量恰好就是当前扫描位置的原数组值a[i]。这个视角和差分数组是同一件事的两种语言差分数组的语言d[i] a[i] - a[i-1]正差分是“新开”负差分是“关闭”。积木的语言原数组a[i]就是当前高度上升多少就要新拿多少块积木下降多少就放回去多少块。“答案等于所有正差分之和”这个结论本质就是在说每一块新拿的积木都对应一次区间加操作而下降时复用之前已经拿在手里的积木不需要额外操作。2.2 为什么从左到右扫一遍就能出答案关键的贪心点在这里区间没有长度限制没有数量上限也没有“某个位置只能作为端点多少次”的约束所以所有“打开的区间”是完全等价的。这意味着在从左到右扫描的过程中我根本不需要记录“具体是哪些区间还开着”只需要记录“还有多少个区间开着”。遇到下降时随便关掉任何一个开着的区间效果都一样。这就是无后效性当前的选择不会影响后续任何决策的最优性。既然没有后效性贪心就成立了。用数学语言描述这个扫描过程cur 0 ans 0 for i in 1..n: delta target[i] - target[i-1] // 也可以直接算差分 if delta 0: ans delta cur delta注意cur其实就是target[i]本身如果目标数组合法非负cur永远不为负。整个过程没有任何分支决策没有优先队列一个 for 循环就结束了所以题目难度只是普及而不是更高。写到这里顺便提一句ans sum(max(0, a[i] - a[i-1]))这个公式在很多题里都出现过比如经典的“粉刷栅栏”模型。如果你在考场上能快速把它和差分数组对上号省下来的时间相当可观。2.3 一个需要警惕的隐藏条件前缀和不能为负上面推导有个前提从全 0 数组开始只用“区间整体加 1”操作得到的结果数组必然所有位置都大于等于 0。所以差分数组的任意前缀和也就是原数组值必须非负。如果题目给出的目标数组是[1, -1, 1]这种那直接用正差分之和就会出错因为根本不可能从全 0 通过区间加得到负数。遇到这种情况要回头检查题目是不是允许负数或者是不是存在两种操作加和减。很多新手在这上面翻车不是因为贪心不会而是因为做题前没有确认“可达性”。判断可不可达也很简单扫描时如果cur出现负数说明无法达成目标直接输出-1或者按题面要求处理即可。3. 落码实战P7871 这类题的完整编码流程3.1 读入、差分、扫描三段式我把这类题的代码组织成固定的三段式减少思考负担。第一段读入原数组a[1..n]注意下标从 1 开始并且把a[0]看作 0。第二段计算差分。如果题目给的是“初始数组”和“目标数组”就先把差值数组算出来再求差值数组的差分。如果题目是从全 0 构造目标就直接对目标数组求差分。这里的核心公式是d[i] a[i] - a[i-1];第三段扫描差分数组累加所有正差分。可以用一个long long保存答案因为n最大到 1e5、值域最大到 1e9 时正差分之和可以达到 1e14 级别int必炸。3.2 一个可以直接套用的 C 模板#include bits/stdc.h using namespace std; const int MAXN 200005; long long a[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { cin a[i]; } long long ans 0; for (int i 1; i n; i) { if (a[i] a[i - 1]) { ans a[i] - a[i - 1]; } } cout ans \n; return 0; }就这么短。很多人第一次看到这个代码会怀疑真的就这么简单对当题目条件就是“无限制的区间加、求最小次数”时核心逻辑确实只有这几行。真正需要花时间的是读题和建模不是写码。如果题目给的是初始数组s和目标数组t只需要把循环里的比较对象换成差值long long pre 0, ans 0; for (int i 1; i n; i) { long long curVal t[i] - s[i]; // 当前还需要加多少 long long preVal t[i - 1] - s[i - 1]; // 上一个位置还需要加多少 if (curVal preVal) ans curVal - preVal; }本质上就是一个通用公式把所有“上升沿”的幅度加起来。3.3 常见的考点变形别被包装迷惑这类题最常见的变形有这么几种变形类型特征处理思路任意区间加求最小次数区间无限制答案 正差分之和判断可行性目标数组可能不可达扫描时记录前缀和出现负数则不可行恰好 K 次操作问“刚好用 K 次能否达成”先求最小次数再判断差值能否通过额外操作补足区间长度固定每次操作的区间长度相同需要把左端点事件和右端点事件配对可能要用队列或堆端点容量受限某些位置不能作为左/右端点配对时跳过受限位置贪心选择优先级变复杂我在做题时见过很多题把同样的模型包了一层奇幻背景什么“贤者施法”“芙兰的弹幕”“谜题石板”剥开之后还是那个“上升沿求和”的内核。所以别被题面吓住把“区间操作”和“最少次数”这几个词圈出来差分数组就该登场了。4. 进阶当“贪心”不够用反悔贪心怎么接住4.1 什么时候不能再无脑累加基础模型能直接用是因为打开的区间完全等价。可一旦题目加了限制比如“每次操作的区间长度必须恰好为 K”或者“每个位置作为左端点的次数不超过某个值”等价性就被打破了。这时候你会发现扫描到某个位置要关闭区间时得从若干个还开着的区间里挑一个关而挑哪个会直接影响后面的可行性。举个例子。如果区间长度固定为 K那么一个左端点l只能和右端点r l K - 1配对。扫描过程中正差分产生的“可关闭区间”不再位于一个等待队列里任意挑选而是有严格的距离限制。如果用基础的“正差分之和”公式结果必然出错。这时候就需要更高级的贪心策略反悔贪心。4.2 反悔贪心的核心思想反悔贪心的本质是先按某种局部最优策略做决定同时把已经做出的决定放进一个优先队列里。当后续遇到更优的决策时允许把之前的决定撤销或替换。用最经典的“汽车加油”问题来理解沿途每个加油站有不同油量油箱容量有限问最少加几次油能到终点。朴素贪心是“没油了才加”但加哪个站的油呢正确做法是每经过一个站就把油量放进堆里没油的时候取堆里最大的那个站加油。这个“取堆顶”的动作就是一种反悔——我并没有在路过时立刻决定加油而是一直在保留选择权等必须加油时再选最优的那个。回到差分模型如果某些位置不能作为端点或者配对距离受限我会把可用的正差分位置存进堆里遇到需要关闭的负差分位置时从堆里挑一个“最合适”的来配对。如果后面发现这个配对导致后续无法完成就再从堆里调整。这个“先推迟决定、遇事再选择、必要时替换”的套路就是反悔贪心的全部秘密。4.3 一个方向性的模板思路下面给一个抽象伪代码展示这个思路的骨架。假设我们要判断“固定长度 K 的区间加能否达成目标”// delta 数组是目标值相对初始值的差分 priority_queueT heap; // 堆里存可用的左端点 for (int i 1; i n 1; i) { if (delta[i] 0) { // 这些正差分可以作为左端点暂时不决定使用先放入堆 把 i 加入堆中次数为 delta[i]; } if (delta[i] 0) { // 需要关闭 -delta[i] 个区间必须从堆里取出合法的左端点 while (需要关闭的次数 0) { 从堆里取一个最合适的左端点 l; if (i - l 1 ! K) { // 长度不匹配可能需要反悔调整堆顶或判定不可行 } 配对一次次数减 1; } } }这段代码我只给方向不把它当作标准答案因为不同题目的限制会导致堆的排序关键字完全不同。但思路是一致的正差分先“存着”负差分来的时候再“配对”配对规则由题目限制决定必要时用堆实现反悔。写这种题最容易犯的错是“过度设计”。很多题目其实用不到反悔贪心——基础贪心已经足够只是你被题面吓住硬给自己加难度。我的建议是先把最简单的情况模拟一遍确认是否真的存在“两个选择效果不等价”的情况再考虑上堆。5. 我踩过的坑和给后来者的三条建议5.1 数据范围、long long 与初始化第一个坑就是int溢出。差分数组的正差分之和上限是n * max(a)当n 1e5、max(a) 1e9时答案是1e14int直接爆掉。洛谷这类普及题很容易把数据范围顶到 1e5 和 1e9所以读入数组、算答案、维护当前扫描值全部用long long别心存侥幸。第二个坑是边界。我第一次写这类题时经常忘记把a[0]初始化为 0。如果数组是 1-indexeda[0]默认是全局变量还好如果写在函数里忘了初始化或者题目从 0-indexed 读入循环里a[i] - a[i-1]就会在i 0那一下出错。老老实实把a[0] 0写成显式赋值或者循环从 1 开始都能避开。第三个坑是差分数组的哨兵位置。目标数组的差分有一个db[n1] -a[n]因为a[n1] 0这个位置虽然通常不会被扫描但在推导可行性时会用到。特别是当你把“区间操作”翻译成“d[l] 1, d[r1] - 1”时r1可能等于n1这个哨兵必须存在否则模型不完整。5.2 别跳过推导直接在考场套公式我见过不少选手看到“区间加”就写上sum(max(0, a[i] - a[i-1]))结果题目一问“能否用恰好 K 次操作完成”就懵了。原因很简单他们不知道公式是怎么来的所以无法判断公式还能不能继续用。比如“恰好 K 次”这个问题如果最小次数是m而K m是否可行取决于能否在保持最终结果不变的情况下增加操作次数。通常的做法是找一个区间对它加两次、再对它的子区间减一次——如果题目不允许减操作那就得看能否通过“长度 1 的区间”来凑。这些细节完全依赖题面不可能靠一个公式通吃。所以我强烈建议平时练题时把“正差分之和”这个结论从头推导一遍尤其是用本章第二节的“开区间/关区间”模型。一旦你理解了每一块正差分对应的是一次新操作你就能灵活应对各种变体。5.3 如何训练这类“标签识别”能力最后聊聊能力怎么练。每次看到一道题先在草稿纸上写下三个信息题面里的操作是什么、要求的最优目标是什么、数据范围是什么。然后问自己操作能不能被差分数组拆成端点事件如果能答案大概率依赖某种扫描或贪心。给自己定一个小目标连续做 10 道“区间加 最小操作次数”的题不求难度高但求每道都写出“差分推导 扫描代码”完整过程。做完之后你会发现这类题在洛谷上就像一个模子刻出来的——背景换得再花哨内核纹丝不动。到那时P7871 在你眼里就不再是“芙兰、姆Q、贤者”的谜题而是明明白白的“差分数组 贪心扫描”模板题。我个人更推荐从“积木搭高度”的视角去理解这个模型它会让你在面对“为什么答案等于上升沿之和”时有一种直觉所有上升都是必须付出的成本所有下降都是免费的红利。想通了这一点贪心就不再是背诵的结论而是真正长在脑子里的思维方式。