P7871这道题最近在洛谷 Wdoi-4 题单里刷到题面带着芙兰、姆Q这些东方梗乍一看挺迷惑人。实际把题目翻译成算法语言就是非常典型的“贪心 差分数组”题难度定在普及相当准确不需要高深数据结构难的是思维转化。这篇把整个思考过程、差分原理、贪心证明、代码实现和考场踩坑一次性讲透适合刚学完差分数组但不太会用的选手也适合想快速搞定普及区间操作题的 OIer 直接抄作业。1. 题目背景与模型转化1.1 题面到底在考什么很多同学看到“芙兰姆Q贤者与谜题”这种标题第一反应是题面在整活。但 OI 题再花哨核心永远是一个干净的数学模型。Wdoi 系列是东方Project 主题本质还是标准算法题。P7871 的常见核心模型可以翻译成下面这句话给定一个长度为 n 的目标数组 b初始时所有位置的值都是 0。每次操作可以选择一个连续区间 [l, r]把区间内所有位置的值 1。问最少操作多少次才能让整个数组正好变成 b。这类“初始全零、区间整体加 1、求最少操作次数”的模型在题目里换个皮肤反复出现。比如铺路、建桥、浇花、覆盖瓷砖本质都是同一道题。P7871 只是把场景包装成了幻想乡里的谜题剥掉外壳后要解决的就是上面这个区间修改计数问题。为什么说它适合普及因为暴力模拟非常直观每次枚举区间、循环加 1但复杂度 O(n×m) 直接爆炸。而正解的代码只有十几行核心是“差分数组 一次线性扫描”。难点不在代码量而在你能不能想到把“区间修改”转换成“单点修改”来统计。1.2 为什么第一步就想到差分数组遇到区间加、区间求和这类问题第一反应应该是前缀和与差分。这两个东西是互逆操作前缀和用来 O(1) 查询区间和差分用来 O(1) 修改区间值。这道题虽然没有强制要求维护动态数组但“区间 1”这个操作本身天然指向差分。差分数组的核心思想是不直接记录每个位置的值而是记录相邻两个位置的差值。这样一来对原数组区间 [l, r] 做整体加 1在差分数组上只影响两个位置d[l] 加 1d[r1] 减 1。区间修改从 O(区间长度) 降到了 O(1)。但这道题经常有人绕不过弯既然要统计最少操作次数为什么不是模拟操作而是建差分因为目标数组 b 是给定的b 的差分数组实际上是“最终状态”的压缩表示。我们不是用差分去维护过程而是通过差分来数出为了形成这个最终状态至少需要多少个“区间左端点”和“区间右端点”。差分数组在这里充当的是计数工具不是修改工具。2. 差分数组入门与核心原理2.1 差分数组的构建与区间加先花一分钟把差分的基础敲实。假设有一个数组 a下标从 1 到 n并且人为定义 a[0] 0。那么差分数组 d 定义为d[i] a[i] - a[i-1]其中 i 从 1 到 n。可以用一个生活类比a 是每个月的账户余额d 就是每个月相比上个月多存了还是少存了多少钱。余额是存量差值是增量。知道了每个月的增量从月初余额 0 开始累加就能还原出每个月的余额。对原数组执行“区间 [l, r] 加 1”时差分数组的变化是d[l] 加 1因为 a[l] 比 a[l-1] 大 1 了d[r1] 减 1前提是 r1 不超过 n因为 a[r1] 没有跟着加但 a[r] 加了所以差值缩小 1其他位置的 d 值完全不变。这就是“区间修改转两次单点修改”的核心。需要注意最后一个位置的情况如果 r 正好等于 n那么 r1 n1 已经超出原数组范围这时我们需要把差分数组多开一位让 d[n1] 也能记录这个 -1。这一步很多人第一次写会漏后面常见问题部分我会专门讲。2.2 从差分视角看待目标数组现在把目光放到这道题本身。初始数组全 0那么初始差分数组也全 0。目标数组是 b目标差分数组我们记为 tt[1] b[1] - 0 b[1]t[i] b[i] - b[i-1]i 2..nt[n1] 0 - b[n] -b[n]这里把差分数组扩展到 n1 位非常重要因为一次区间操作往右端点后面“塞”的那个 -1最终都得落到某个位置上。如果不扩展这一位差分数组的总和不为 0统计正项时就会漏掉收尾的负项。于是问题变成了我们有一个全 0 的差分数组每次操作等价于在某个位置加 1、在后面某个位置减 1要求最终恰好变成 t。一次区间操作就像在差分数组里放置一对“正负电荷”一个 1 标记区间起点一个 -1 标记区间终点。所有区间操作的总数就是需要放置的这样的“电荷对”的数量。这个转化最大的好处是我们不再关心区间具体覆盖了哪一段只需要看 t 里有多少个正的“起点”、多少个负的“终点”。统计最少操作次数的问题被简化成一个计数问题。3. 贪心思路与最优性证明3.1 关键观察正负差分如何配对现在 t 数组已经摆在我们面前。目标差分数组的特点是所有项加起来等于 0。所以正数之和的绝对值一定等于负数之和的绝对值。这个“正数总和”其实就是答案的候选。为什么因为每次操作都会产生一个 1 和一个 -1。从全 0 差分变成 t所有正数项必须“凭空出现”出来而每次操作最多让差分数组的正项总和增加 1。因此正项总和是多少操作次数就至少是多少。贪心策略也很简单从左到右扫描目标差分数组用一个计数器 cnt 表示“当前还开着多少个区间”。遇到正数 x说明这里有 x 个区间要开始cnt 加 x遇到负数 -y说明这里有 y 个区间要结束cnt 减 y。因为题目保证最终数组非负cnt 在扫描过程中永远不会变成负数。扫描到 n1 位时cnt 正好归零。这个扫描过程本质上就是在给每个区间左端点寻找合适的右端点。正项提供左端点负项提供右端点从左到右配对先开始的区间先结束天然满足区间合法性。3.2 为什么贪心是最优的很多题解直接告诉你“答案等于正差分之和”但不讲为什么。这里把下界和构造都补上你以后遇到变体也能自己推导。先证下界。设最终差分数列为 t它的正项总和为 S。初始差分数组全是 0正项总和为 0。一次区间 1 操作在差分数组中只引入一个 1、一个 -1。这个 1 顶多让正项总和增加 1不可能增加更多。所以要从正项总和 0 变到 S至少需要 S 次操作。这个结论和区间怎么选无关是数学上的硬下界。再证可达。按照上面“从左到右扫描、维护 cnt”的贪心过程每个正项 x 就当作 x 次操作的起点每个负项 -y 就当作 y 次操作的终点。因为目标数组 b[i] 等于差分前缀和而 b[i] 非负所以 cnt 始终等于当前覆盖次数 b[i]不会为负。扫描结束时 cnt 变成 0所有开过的区间都正确关闭了。这说明 S 次操作一定可以构造出来。下界和上界相等最优解就是 S。这个证明思路在贪心题里非常通用先证一个操作下限再构造一个操作方案达到下限两点夹逼最优性成立。3.3 注意事项边界位置与正负号判断实现的时候有几个细节容易翻车。第一差分数组一定要考虑 n1 位因为最后一个负项往往落在那里如果你只算前 n 位的正项之和会得到错误答案。第二统计正项时只统计严格大于 0 的差值差值为 0 说明高度没变化不需要新的操作。第三如果直接读入目标数组并实时维护上一个值空间复杂度可以压到 O(1)完全不需要真的存下整个差分数组。另外强调一下如果题目保证 b 数组非负那么从左到右贪心配对一定合法如果 b 可能出现负值那题面通常会有额外说明贪心模型也需要重新审视。竞赛里大部分这类题都保证目标值非负遇到不保证的题目先确认清楚。4. 代码实现与复杂度分析4.1 C 代码最短实现直接给可以 AC 的代码。核心公式就一行答案等于 b[1] 加上所有“上升高度”之和。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; long long ans 0; long long last 0; for (int i 1; i n; i) { long long x; cin x; if (x last) ans x - last; last x; } cout ans \n; return 0; }这段代码为什么对每次读入 x 作为当前目标高度如果 x 比上一轮 last 高说明差分数组在这个位置出现了一个正的差值 x - last这个正差值就是必须新增的操作数量。如果 x 比 last 矮或者相等差分值是负数或 0不需要统计。初始时 last 0等价于 b[0] 0所以 b[1] 的上升高度也被正确计入。如果你更希望把逻辑写清楚、便于考场检查可以用差分数组版本#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long b(n 2, 0); for (int i 1; i n; i) cin b[i]; long long ans 0; for (int i 1; i n 1; i) { long long diff b[i] - b[i - 1]; if (diff 0) ans diff; } cout ans \n; return 0; }第二个版本把 n1 位也纳入统计。因为 b[n1] 默认是 0所以 diff 的最后一项是 -b[n]通常是负数不会干扰答案。两个版本在非负输入下等价选你觉得好理解的写。4.2 复杂度分析O(n) 扫描O(1) 额外空间时间复杂度只取决于读入和一次线性扫描严格 O(n)。空间方面第一种写法只存一个 last 变量额外空间 O(1)即使目标数组长度到 10^6 甚至 10^7内存也毫无压力。这也是差分题最舒服的地方思维绕但代码实现轻。普及的题通常 n 在 10^5 到 10^6 级别O(n log n) 也能过但 O(n) 的写法更漂亮而且不会因为排序、二分引入额外出错点。4.3 题目变体与扩展思路掌握了“目标差分正项之和”这个核心后可以快速迁移到几种常见变形如果把“区间 1”改成“区间加任意值 w”答案变为所有正差分除以 w不完全是正确做法是把每个正差分值除以 w 上取整。因为每次操作能贡献的最大正增量是 w。典型题目比如“区间加 k 求最少次数”。如果初始数组不是全 0而是给定的另一个数组 a目标是变成 b那么先算目标差分减去初始差分再统计正项之和。本质是求两个数组之间的“转换代价”。如果要求输出具体操作方案可以在扫描差分数组时把左端点位置存入队列遇到负项时弹出相应数量的左端点组成区间输出。这个思路在构造题里很实用。这些扩展不要求你现在就完全掌握但要知道差分数组提供的是一种“区间修改转单点事件”的表述方式具体怎么用永远取决于题目让你统计什么。5. 常见问题与排查技巧实录5.1 为什么答案不是“数组中的最大值”这是很多新手最容易踩的坑。有同学看到目标数组最高峰是 5就觉得答案应该是 5 次因为每个位置最多被覆盖 5 次。这个想法只对“数组先单调上升再单调下降”的情况成立。举个例子b [3, 1, 3]最高峰是 3。按最大值答案应该是 3但正确答案是多少我们手算差分t [3, -2, 2, -3]正项之和为 3 2 5。构造操作位置 1 开启 3 个区间其中 2 个在位置 2 结束即区间 [1,1] 做 2 次剩下 1 个延续到位置 4 结束即 [1,3] 做 1 次位置 3 开启 2 个区间都在位置 4 结束即 [3,3] 做 2 次。总操作 5 次。中间位置 2 被覆盖 1 次不是最高的但两次“上升”分别在开头和结尾导致正差分累计变大。所以遇到这种“双峰”“多段起伏”的数组老老实实用差分正项和不要凭直觉看最大值。5.2 差分数组需要扩展到 n1 位吗需要。这是一个很容易被样例隐藏的问题。当区间右端点是 n 时操作会在差分数组的 n1 位置产生一个 -1。如果你只开长度为 n 的差分数组这个 -1 就被丢弃了统计正项时看似没影响但如果后面有题目让你对差分数组求和检查你会发现自己怎么都对不上。用差分数组版本时直接循环到 n1让 b[n1] 默认为 0就能自然处理这个边界。用 O(1) 版本时由于我们只关心“上升高度”这个边界负项天然不影响答案所以代码可以忽略它。但理解上必须知道它的存在。5.3 为什么 int 会出锅目标数组的值可能很大尤其当 n 很大且允许高度累计时答案可能超过 2^31。竞赛中的坑题经常在这里埋雷你输出 int本地小样例全对提交后 WA 或 RE。我的建议是涉及答案累加的变量一律开 long long读入也直接用 long long。反正 long long 又不慢别在这种地方省。5.4 考场上如何快速验证贪心正确性我自己常用的方法是拿到题先写一个最暴力的小数据生成器随机生成目标数组再用 BFS 或递归枚举所有可能的区间操作算出真正的最小操作次数。然后把差分公式的答案和暴力答案对拍。数据规模 n 不超过 8两秒内就能跑完。对拍通过后再提交正式代码心里踏实得多。这个习惯特别适合普及的贪心题。很多贪心策略光看证明觉得没问题一写代码就漏边界对拍能在 5 分钟内把问题暴露出来。易错点错误表现正确做法数组最大值当作答案多峰数据 WA用正差分之和忘记 n1 边界差分检验不过差分数组多开一位int 存答案大样例溢出全程 long long只算正项没处理负项感觉代码缺逻辑记住总和为 0正项即答案6. 实战调试与心得补充6.1 手算样例的完整过程以目标数组 b [2, 5, 3, 4] 为例完整走一遍差分流程。初始 last 0读入 22 0ans 2ans 2last 2读入 55 2ans 3ans 5last 5读入 33 5不更新 anslast 3读入 44 3ans 1ans 6last 4。答案 6。我们可以反过来构造验证区间 [1,3] 做 2 次数组变成 [2,2,2,0]区间 [2,4] 做 3 次变成 [2,5,5,3]区间 [4,4] 做 1 次变成 [2,5,3,4]。总操作 2 3 1 6和公式完全一致。这个手算过程也展示了差分统计的物理意义每次上升都对应新开区间。6.2 从这道题学到的通用思维我个人做完 P7871 最大的收获是贪心题不要急着猜答案先想办法把问题“翻译”成另一种等价表述。差分数组在这里不是用来加速模拟的而是把“区间覆盖次数”转换成“事件数量”。一旦换了个角度答案往往就自己跳出来了。后面遇到类似题目我也会先问自己三个问题题目的操作能不能转成差分单点修改最小代价能不能表示成某种计数下界这个下界能不能被贪心构造达到如果三个问题都是肯定的那这道题基本就是差分 贪心的套路。最后分享一个考场小技巧读题时看到“区间 1”“最少操作次数”“目标数组”这三个关键词同时出现直接写差分正项和公式然后花两分钟用小样例验证。省下来的时间留给后面的难题性价比很高。这道题后续如果想深入可以把输出方案、多组询问、区间加减混合操作都试着实现一遍掌握深度会完全不一样。