★ FEATURED ARTICLE GESP 五级考场上看到相等序列四个字不少同学第一反应是跟字符串、判等、双指针较劲但这道题真正要想清楚的是它考的是差分数组也就是区间整体加减求最少操作次数那一类模型。我带着几个学生复盘这轮认证时发现会差分模板的人几乎能把这道题当秒杀题写没接触过差分的人则普遍卡在怎么把区间拆开。这篇文章按从读题到建模、从原理到代码、从样例到坑点的顺序完整拆一遍适合正在备考五级、以及想补差分应用的同学。1. 题目到底在问什么1.1 先把题面还原成一句话相等序列这个题名在五级真题里大意是这样的给定两个长度相同的整数序列 a 和 b每次操作可以选 a 中任意一个连续区间 [l, r]把区间里每一个数都加 1。问最少操作多少次能让 a 和 b 恰好相等如果无论如何都做不到就输出 -1。不同考点在表述上可能有点出入有的会把加 1说成整体增加一个固定值有的会加一句你只能修改 a但核心模型是一模一样的区间整体增量求最少步数。有人可能会问这个范围有多大通常 n 能到 10^5 级别数值也不会太小这就决定了后面不能靠模拟乱搞。这道题适合谁来读呢正在备考五级的同学、学完基础排序和枚举后想补算法思维的同学都能从里面拿到东西。它表面上是模拟题内核却是差分数组——一个竞赛里特别好用、但课本上很少系统讲的知识点。见过差分的人这题基本就是送分没见过的人很容易陷进每步都不知道该选哪个区间的泥潭里。1.2 为什么暴力思路一定过不了第一反应往往是模拟每次都扫一遍 a 和 b发现哪里不等就选一个区间加 1。这种思路有两个致命问题。第一区间数量是 O(n^2) 级别的假设答案要执行 k 次操作每次判断当前数组是否相等又要 O(n)总复杂度能到 O(k * n^3) 的水平n 一旦过万想都不用想。第二也是更本质的问题你根本不知道最优策略长什么样。先加 [1,3] 再加 [2,2] 可能成功先加 [2,2] 再加 [1,3] 也可能成功中间状态五花八门顺着操作顺序去猜永远没有尽头。所以这题的突破口不是模拟而是换一个视角看区间加这件事。你需要一个工具把一段区间上的整体变化拆成端点上的独立变化。差分数组就是干这个的。2. 差分数组把区间操作变成两个单点操作2.1 差分到底在干嘛差分数组的定义很朴素对序列 c[1..n]令 d[1] c[1]d[i] c[i] - c[i-1]i ≥ 2。反过来c[i] 就是 d[1] d[2] ... d[i]也就是说原序列是差分数组的前缀和。差分最大的本事在于区间修改在差分数组上会退化成两次单点修改。这里要稍微提醒一下很多同学在学校里见过差分但只停留在区间加、最后单点查的经典用法上也就是把差分数组累加回去还原原数组。而这道题需要换一个方向用我们不关心中间过程长什么样只看要让两个序列相等差分数组需要发生什么变化。把这个方向想通答案就自己浮出来了。我建议不太熟悉的读者先别管考试难度把差分当成一个普通技能练熟。它不依赖复杂数学本质就是把大家一起变的信息拆成起点变一点、终点变一点的信息。2.2 一次区间加在差分数组上留下什么痕迹设 need[i] b[i] - a[i]表示位置 i 还需要增加多少才能追上 b。一次对 a 的 [l, r] 区间加 1等价于 need[l..r] 全部减 1。现在给 need 做差分D[i] need[i] - need[i-1]并且补上边界 need[0] 0、need[n1] 0。一次 need[l..r] 减 1对 D 的影响是什么只有两个地方变化need[l] 减 1会让 D[l] 跟着减 1need[r] 减 1会让 need[r1] 相对 need[r] 的差变大 1也就是 D[r1] 加 1。至于中间那些位置相邻差值一点都没变。换句话说一次区间操作在差分数组上表现为某个位置减 1、另一个位置加 1。原来一个连续段的事现在变成了两个单点的事。这就是全题最关键的转化后面所有推导都是在这个转化上长出来的。2.3 全部相等在差分视角下是什么如果 a 已经等于 b那么 need 全 0差分 D 也全 0。反过来如果 D 全 0由于 need[0] 0用前缀和从前往后推need 也全 0。所以使 a 等于 b和把 D 变成全 0 数组是同一件事。我们手里的操作变成了每次选一个位置加 1、选另一个位置减 1。那原问题就等价于从初始的 D 出发每次让一个正数减少 1、让一个负数增加 1也就是负数的绝对值减少 1最少多少次能全部归零。这里有一个值得展开的下界论证每一次操作只能让 D 里所有正数的总和减少 1。因为正数总和一开始就固定了所以操作次数至少是初始 D 中正数的和。那这个下界能不能够到关键要看配对时机。当所有 need[i] 都大于等于 0 时D 从前往后的前缀和始终非负正差分总能出现在它需要关闭的负差分之前整个过程像一个括号序列左括号永远在对应右括号前面。于是从左到右扫遇到正数就开启若干区间遇到负数就关闭若干区间总能构造出步数恰好等于正数和的方案。这就是为什么最终答案不用费劲构造区间直接数正差分就行。2.4 最少操作次数如何数出来实际操作时你不需要真的去构造区间。答案就是 sum(max(D[i], 0))把所有正差分加起来即可。负差分根本不用管因为整个 D 数组的和等于 need[n1] - need[0] 0正数总和和负数绝对值总和必然相等你把正数消干净的同时负数也自动归零了。举个例子。a [0, 0, 0]b [1, 2, 1]。need [1, 2, 1]差分 D [1, 1, -1, -1]差分长度是 n1正数和是 2答案就是 2。构造过程也直观先操作 [1, 3]a 变成 [1, 1, 1]再操作 [2, 2]a 变成 [1, 2, 1]。两步完成。这个例子特别能说明问题表面上有三个位置要加其中中间位置还是 2所有 need 加起来是 4但真正的最优解只需要 2 次因为区间可以重叠覆盖。差分正数和恰好抓住了区间覆盖的本质。3. 完整实现与代码拆解3.1 无解判断只允许加 1 时的特判在这个版本的题目里每次只能加不能减所以一旦某个位置出现 b[i] - a[i] 0也就是 a 已经大于 b 了那无论以后怎么用区间覆盖这个位置它只会变得更大永远不可能回到和 b 相等。这一条判断直接输出 -1。这里有个容易误解的点是不是所有 need[i] 0 就一定无解正好相反是所有 need[i] 0 时一定有解。原因就在前面说的配对可行性need 前缀和始终非负D 的正负号可以按顺序配对不会出现负数差分找不到左边的正数去匹配的情况。所以无解判断只需要一个 if不需要额外推导任何复杂条件简单到有些同学反而不信。3.2 参考代码与逐段解释上代码。这里的实现没有单独开差分数组而是用一个 pre 变量滚动保存 need[i-1]这样既省空间又不会在访问 D[n1] 时越界。环境按 C17 写绝大多数等级考试环境都能直接编译。下面这段是完整可运行的你直接抄到本地跑样例就知道效果。我在关键位置写了注释但真正上考场时建议只保留最少的注释因为判题只看结果不看你注释写得美不美。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n 1), b(n 1); for (int i 1; i n; i) cin a[i]; for (int i 1; i n; i) cin b[i]; long long ans 0; long long pre 0; // pre 记录 need[i-1]初始 need[0] 0 bool ok true; for (int i 1; i n; i) { long long need b[i] - a[i]; if (need 0) ok false; // 只允许加 1 时这项为负必无解 long long d need - pre; // D[i] need[i] - need[i-1] if (d 0) ans d; // 累加正差分 pre need; } // 补上 D[n1] need[n1] - need[n] 0 - need[n] long long last 0 - pre; if (last 0) ans last; cout (ok ? ans : -1) \n; return 0; }几个细节展开说一下。差分数组其实不用真的开出来因为我们只需要正差分和而每次知道 need[i] 和 need[i-1] 就能算出当前差分pre 这个变量就是用来保存 need[i-1] 的。至于 D[n1]它是 0 - need[n]当所有 need 非负时它一定小于等于 0本来不需要处理。但写上去更稳健万一题目改口允许减、或者你以后做别的差分题这个边界就不会漏。3.3 复杂度与数据范围整个算法只做了一趟线性扫描时间复杂度 O(n)额外空间 O(1)。这比暴力不知道高到哪里去了。需要注意数值范围b[i] - a[i] 本身可能到 10^9差分正数的累加在极端数据下能到 10^14所有涉及差值的变量必须用 long longint 必炸。n 到 10^5 时 O(n) 毫无压力就算 n 到 10^6 也能跑。考场上只要一眼看出差分这道题的耗时基本就是读入和输出时间。4. 同类变体看清出题人的小算盘4.1 变体一允许加也允许减如果题目改成每次操作可以把一个区间整体加 1 或减 1那就不存在无解的情况了因为每个位置都能双向调整。此时答案依然是差分正数和原因是完全对称的每操作一次正差分总量减少 1负差分绝对值总量也减少 1正数总和与负数绝对值总和相等把正数消成 0 的同时负数已经消干净了。这种变体在设问上往往喜欢绕一下比如不给两个序列而是给一个初始全 0 的数组和一个目标数组问至少多少次区间加减能得到目标。本质上就是把目标数组直接当作 need 数组差分照样做思路完全一致。记住一个判断标准只要操作是区间整体变就优先往差分上靠。4.2 变体二每次选两个位置一加一减还有一种常见亲戚题给定数组每次可以任选两个下标 i、j让 a[i] 加 1、a[j] 减 1问最少几次能把所有元素变相等。这题先判断总和能不能被 n 整除能整除的话目标值就是平均数然后算每个位置和平均数的差答案就是所有正差值之和也就是负差值绝对值的和。比如 a [1, 2, 3]平均数是 2差值分别是 -1、0、1答案就是 1 次把 a[3] 减 1 补给 a[1]得到 [2, 2, 2]。这题和差分的区别在于每次改动的是任意两个位置而不是某个区间的两端配对不受先后顺序约束所以模型更简单。对比下来你会发现区间操作的题大多靠差分变形任意两点交换的题大多是总量守恒。看题第一步永远要问自己这个操作对应到信息的流动上是几个点4.3 变体三删除元素使序列相等如果相等序列的题面写的是每次可以删除一个元素问最少删除几个元素能让两个序列相等那这就和差分无关了而是最长公共子序列LCS问题两个序列都保留它们最长的公共子序列删除次数 n m - 2 × LCS 长度。五级考纲虽然不强制要求背 LCS 模板但递推和简单动态规划的思想在五级是要求初步掌握的所以这种变体也不是没可能出现。所以拿到题目第一步永远是确认操作类型。同样是相等序列四个字操作不同算法天差地别。我把常见模型整理成一张表考前扫一眼至少能帮你快速定位题目想考什么。操作方式对应模型答案形式区间整体加 1不能减差分数组差分正数和存在负 need 则无解区间整体加减 1差分数组差分正数和无无解任意单点加减 1逐位统计sum(abs(a[i] - b[i]))任意两点一加一减总量守恒总和能被 n 整除时 sum(正的 excess)删除一个元素最长公共子序列n m - 2 × LCS 长度5. 考场上最容易踩的坑5.1 差分数组开多大、边界怎么处理差分数组长度是 n、n1 还是 n2这是新手高频出错点。因为我们规定 need[0] 0 且 need[n1] 0所以差分下标可以取到 n1。如果用裸数组记得开 n2别开 n 就完事。像上面的参考代码那样用滚动变量 pre 来写能直接避开下标问题也不容易在边界上犯迷糊。差分题最常见的运行时错误就是数组越界而越界往往不会立刻报错反而会给你一个看似正常的错误答案特别坑。5.2 忘记用 long long我在模拟考里见过不少同学样例全过一交上去大数据就 WA最后排查发现就是 int 溢出。b[i] - a[i] 可能到 10^9差分正数的累加在极端数据下到 10^14int 连一个位置都存不下。而且这类问题往往不是每跑必错而是特定数据触发没有对拍很难发现。凡是跟差值、累加沾边的变量一律按 long long 写这是五级考试里经常出现的隐藏陷阱。5.3 无解判断写反无解条件本身很简单存在 b[i] a[i] 就输出 -1。但有些同学会写反成所有 b[i] a[i] 才输出 -1方向一错样例可能还能碰巧过一到有解和无解混合的数据就全崩。还有一种错误是判断了无解却忘了在输出时分支导致无解数据输出一个莫名其妙的步数。建议把 ok 变量一路带到输出阶段先统一计算最后统一判断这样两个分支就不会串。5.4 样例过了但未必对对拍思路这题样例往往只有一两组覆盖不了全部边界。我在家给某同学讲这道题时让他写了一个暴力程序n 很小每次枚举所有区间用 BFS 找最少步数然后和差分程序做对拍。随机造几千组 n 8、数值范围 0..5 的数据几分钟就能验证正确性。对拍脚本的思路很简单三个程序一个数据生成器、一个暴力程序、一个被测程序跑同样的输入比较输出。如果你只会写被测程序可以让朋友帮你写个暴力版或者事后自己补。数据生成器用 Python 写最方便下面这段随机生成合法输入配合 bash 循环就能跑对拍import random n random.randint(1, 8) print(n) print(*[random.randint(0, 5) for _ in range(n)]) print(*[random.randint(0, 5) for _ in range(n)])for i in $(seq 1 1000); do python3 gen.py in.txt ./brute in.txt out1.txt ./solve in.txt out2.txt if ! diff -q out1.txt out2.txt /dev/null; then echo WA on test $i break fi done为什么一定要强调对拍因为差分题的典型特殊数据很多a 和 b 完全相同答案是 0、所有 need 全相等、need 呈中间高两边的山峰形、n 1 的单序列。这些边界靠肉眼很难全部想到而对拍能帮你自动覆盖。把这组数据都跑过一遍代码才敢说稳了。6. 写在最后的几句经验我带着学生们复盘这轮五级考题时最大的体会是这道题真正卡人的不是差分公式而是愿不愿意把区间操作看成端点操作。很多人不是不会算差分是根本没往那边想总想着模拟或者贪心选区间。其实差分是一个非常稳定的思维定式看到区间整体加、整体减、整体赋值第一反应就是差分看到要求最少次数第二反应就是数差分里的正数。这个定式一旦建立相等序列这种题就变成了读题后三十秒内能识别出模型的题目。备考时建议把最近几轮等级认证真题里所有涉及区间操作的题集中刷一遍熟练之后你会发现出题人只是换着不同的场景包装同一件事。最后再分享一个小技巧考场上如果拿不准答案公式就手动构造一组小数据比如 a [0, 1, 0]、b [1, 1, 1]自己推一遍差分答案对得上再往代码里填。这样至少能避免公式记反、边界漏掉的问题。
阅读完成 · 觉得有帮助？
