GESP五级真题解析：差分数组秒解“相等序列”问题

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[n+1] = 0。一次 need[l..r] 减 1，对 D 的影响是什么？只有两个地方变化：need[l] 减 1，会让 D[l] 跟着减 1；need[r] 减 1，会让 need[r+1] 相对 need[r] 的差变大 1，也就是 D[r+1] 加 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[n+1] - need[0] = 0，正数总和和负数绝对值总和必然相等，你把正数消干净的同时，负数也自动归零了。

举个例子。a = [0, 0, 0]，b = [1, 2, 1]。need = [1, 2, 1]，差分 D = [1, 1, -1, -1]（差分长度是 n+1），正数和是 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[n+1] 时越界。环境按 C++17 写，绝大多数等级考试环境都能直接编译。下面这段是完整可运行的，你直接抄到本地跑样例就知道效果。我在关键位置写了注释，但真正上考场时建议只保留最少的注释，因为判题只看结果，不看你注释写得美不美。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long 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[n+1] = need[n+1] - 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[n+1]，它是 0 - need[n]，当所有 need 非负时它一定小于等于 0，本来不需要处理。但写上去更稳健，万一题目改口允许减、或者你以后做别的差分题，这个边界就不会漏。

3.3 复杂度与数据范围

整个算法只做了一趟线性扫描，时间复杂度 O(n)，额外空间 O(1)。这比暴力不知道高到哪里去了。需要注意数值范围：b[i] - a[i] 本身可能到 10^9，差分正数的累加在极端数据下能到 10^14，所有涉及差值的变量必须用 long long，int 必炸。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 模板，但递推和简单动态规划的思想在五级是要求初步掌握的，所以这种变体也不是没可能出现。

所以拿到题目，第一步永远是确认操作类型。同样是"相等序列"四个字，操作不同，算法天差地别。我把常见模型整理成一张表，考前扫一眼，至少能帮你快速定位题目想考什么。

5. 考场上最容易踩的坑

5.1 差分数组开多大、边界怎么处理

差分数组长度是 n、n+1 还是 n+2，这是新手高频出错点。因为我们规定 need[0] = 0 且 need[n+1] = 0，所以差分下标可以取到 n+1。如果用裸数组，记得开 n+2，别开 n 就完事。像上面的参考代码那样用滚动变量 pre 来写，能直接避开下标问题，也不容易在边界上犯迷糊。差分题最常见的运行时错误就是数组越界，而越界往往不会立刻报错，反而会给你一个看似正常的错误答案，特别坑。

5.2 忘记用 long long

我在模拟考里见过不少同学，样例全过，一交上去大数据就 WA，最后排查发现就是 int 溢出。b[i] - a[i] 可能到 10^9，差分正数的累加在极端数据下到 10^14，int 连一个位置都存不下。而且这类问题往往不是每跑必错，而是特定数据触发，没有对拍很难发现。凡是跟差值、累加沾边的变量，一律按 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]，自己推一遍差分，答案对得上，再往代码里填。这样至少能避免公式记反、边界漏掉的问题。