“水库溃坝填补”这个题名我最早是在华为OD机试真题列表里看到的编号959。网上流传的版本有细微差别但核心都指向同一个算法模型对连续区间做加1操作求达到目标要求的最少操作次数。这道题拿来做区间类算法的练手题非常合适既不像模板题那样一眼看穿也不至于难到劝退正好卡在“需要你现场建模”的位置上。如果你正在备考OD机考或者单纯想找一道题把差分数组彻底吃透这篇值得认真看一遍。我下面会把题目拆开讲清楚再把C、Java、Python、C、JavaScript五个版本的实现和坑位都过一遍。1. 水库溃坝填补先把题目拆成“区间加”模型1.1 网上流传最广的一版题面我看到的大多数版本题面大致是这样的有一段堤坝被分成N段洪水过后每一段都有一个当前高度记为数组a[i]。现在要抢修目标是把每一段的高度都补到安全高度M以上。每次操作可以选一段连续区间[l, r]把区间内所有堤坝的高度整体加1。问最少需要操作多少次。输入格式通常是第一行两个整数N和M第二行N个整数表示每段的当前高度。比如4 4 1 2 1 3这个样例里四个位置离安全高度分别缺3、2、3、1答案是4次。这个输出是怎么来的后文会详细推一遍。先提醒一句有些题库给的输入是“缺口深度”也就是直接告诉你每段还需要补多少而不是当前高度两种版本的解法只有一个很小的差别后面我会专门讲。1.2 题眼不在“溃坝”在“区间加1”这题最关键的一点是识别出它在考什么。表面上是“修补溃坝”本质上是区间修改计数问题。特点是每次操作影响的是一段连续区间区间内所有元素都加同一个数目标是所有位置达到某个下界求最小操作次数。看到这三个特征就应该条件反射地想到差分数组或者前缀和。为什么不能直接模拟因为一次操作能覆盖很长一段区间最坏情况下需要操作的次数可能到亿级别再乘以N的扫描开销直接超时。N到1e5、差值到1e9的时候模拟一次都跑不完。我见过不少同学拿到题先想着“每次找最低的段把它补起来”然后写了个while循环样例能过一到大数据就凉。这就是没在做题前先做数学建模。把“堤坝高度”抽象成“数组”把“连续区间抢修”抽象成“区间加1”把“最少操作次数”抽象成“差分的正数和”这道题才真正开始变得可解。2. 核心思路用差分数组把O(N*M)优化到O(N)2.1 差分数组为什么能处理区间修改先给不熟悉差分的同学补个基础。对于一个数组b它的差分数组D定义为D[i] b[i] - b[i - 1]通常我们会让D[1] b[1]也就是认为b[0]为0。差分数组有意思的地方在于对原数组b做一次“区间[l, r]整体加1”等价于在差分数组上做两次单点修改D[l]加1、D[r1]减1。这个性质把区间操作变成了O(1)操作代价是需要通过前缀和还原原数组。你可以把差分想成剖面图的斜率变化原数组是地形剖面差分记录的是每两个相邻位置之间的高度跳变。区间加1相当于在剖面图上画一条水平线覆盖某个连续区域水平线的起点会让“斜率”上升终点会让“斜率”下降。回到这道题。设need[i] max(0, M - a[i])表示第i段还需要补的高度。一次“区间加1”操作本质上就是让need数组在某个连续区间[l, r]里的每个位置都减1直到need全部变成0。问题变成初始need数组已知每次可以选一个连续区间让区间内每个数减1最少多少次能全部清零注意初始need可能不是单调的有些位置需要补得多有些补得少。如果我们对need做差分设D为need的差分数组那么一次区间减1在D上表现为D[l]减1、D[r1]加1。所有need归零等价于所有D也归零。这样问题再一次被转译给定差分数组D每次可以把一个正数和后面的一个负数配对正数减1、负数加1问最少配对多少次能把所有D清空答案就是所有正数的绝对值之和因为每一次操作最多只能吃掉一个正数单位。2.2 最少操作次数公式怎么来的严格说这个结论需要两半证明。一半是下界对于每个位置i如果need[i]比need[i - 1]高出一个delta也就是差分D[i] delta 0那么这个高度差delta不可能靠“从更早的区间延续过来”补上因为前面的need更低延续过来的区间如果覆盖到i必然也会覆盖i之前的低位置会让那边的need变成负数也就是让那边的堤坝超过安全高度。既然不能靠延续这delta次操作就必须以i为左端点“重新起头”。所以最少操作次数至少是所有正差分之和。另一半是构造从差分数组的角度只要D中还存在正数就找任意一个正的D[l]和它之后某个负的D[r1]配对执行一次区间减1D[l]减1、D[r1]加1。因为正数和与负数和绝对值相等这个配对过程一定能持续到所有D清零总操作次数恰好是正数之和。所以结论是严格成立的。用前面那个样例来走一遍。初始高度是[1,2,1,3]M4need [3,2,3,1]。need的差分数组D [3, -1, 1, -2, -1]长度为n1末尾虚拟一个need[n1]0。正数有3和1和为4答案就是4。具体操作可以这样凑出来先区间[1,1]加1一次再区间[1,3]加1一次再区间[1,4]加1一次最后区间[3,3]加1一次。把四次操作叠加四个位置分别被补了3、2、3、1刚好全部达标。你可能会觉得这个操作顺序像是凑出来的实际上它就是按照差分配对一步步构造出来的理解了配对过程公式也就记住了。所以代码写起来极其简单不需要真的维护need数组和差分数组只需要遍历一次累加所有need[i] - need[i-1]的正值其中need[0]视作0。核心代码就一个if判断加一个累加。3. C、Java、Py、C、JS五语言实现与避坑3.1 C实现重点C是机考最稳的选择之一代码跑得快STL也方便。这个题甚至不需要STL数组开不开都无所谓因为可以滚动变量。我的实现如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long m; cin n m; long long ans 0; long long prev 0; for (int i 0; i n; i) { long long a; cin a; long long need m - a; if (need 0) need 0; if (need prev) ans need - prev; prev need; } cout ans \n; return 0; }几个细节要注意。第一m和a都用long long因为如果M是1e9某个位置高度是0need就是1e9N是1e5差分的正数和可能到1e14级别int一定会爆。第二输入用cin搭配ios::sync_with_stdio(false)和cin.tie(nullptr)在OJ上速度足够不用自己造快读。第三prev保存的是上一个位置的need初始为0这个0是有含义的堤坝左边界之外不需要补所以第一个位置如果需要补3就相当于相对左侧多出了3次“新开区间”必须计入答案。如果你在VS Code里跑这个题提前把C/C扩展和编译任务配好代码写完直接CtrlShiftB编译别等到考试现场才来折腾环境。这种纯数值题C的编译错误概率很低最容易翻车的就是类型溢出。3.2 Java实现Java的代码结构和C几乎一一对应核心逻辑完全一致。我用的是Scanner读入数据量到1e5级别完全撑得住不需要上BufferedReader也能过。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); long m sc.nextLong(); long ans 0; long prev 0; for (int i 0; i n; i) { long a sc.nextLong(); long need m - a; if (need 0) need 0; if (need prev) ans need - prev; prev need; } System.out.println(ans); sc.close(); } }Java的坑主要在类型上。a如果声明成intm是longm - a会自动提升为long这没问题但如果你把need也声明成intm - a的结果被截断成int大样例直接起飞。所以干脆全部用long。另外注意类的名字必须是Main这是大多数OJ的硬性要求。Scanner用完关掉是个好习惯不关其实也行但写了不亏。3.3 Python实现Python代码最简洁但输入读取这个细节很多人翻车。用input()逐行读在N1e5时勉强能用但用sys.stdin.buffer.read()一次性读入再split性能和代码简洁度都好很多。import sys data list(map(int, sys.stdin.buffer.read().split())) n, m data[0], data[1] a data[2:2 n] ans 0 prev 0 for x in a: need m - x if need 0: need 0 if need prev: ans need - prev prev need print(ans)Python版本需要注意如果a数组很大data切片会产生一个新列表内存翻倍对于1e5级别完全无所谓但如果你在极限OJ上跑1e6可以考虑直接索引遍历不切片。我平时自己刷题习惯切片因为写着清爽。还有一个细节是Python的负索引如果你在循环里想用x if x 0 else 0这种方式别写成prev[-1]之类的东西出错了非常难查。3.4 C实现纯C在这个题里完全够用毕竟不需要字符串处理也不需要复杂的数据结构。C的代码是最面向过程的读一个数算一个数连数组都不用开。#include stdio.h int main() { int n; long long m, a, need, prev 0, ans 0; scanf(%d %lld, n, m); for (int i 0; i n; i) { scanf(%lld, a); need m - a; if (need 0) need 0; if (need prev) ans need - prev; prev need; } printf(%lld\n, ans); return 0; }C语言版本的两个注意点。第一scanf的格式占位符必须写对n是int用%dm和a是long long用%lld写错一个就全乱。第二C语言的零初始化很关键prev和ans必须显式赋0不像全局变量默认是0局部变量如果不初始化里面是随机值这时候程序行为完全不可预测。我在本地编译器可能能跑出正确答案换台机器就错这种问题在考场上是白送命。3.5 JavaScript实现JS在华为OD机试里一般是Node环境不少前端转算法的同学第一反应是写JS但这个题在读取输入上坑最多。不同OJ对JS的输入支持不完全一样有支持/dev/stdin的有只能走readline的。我一般用fs读全部输入兼容性比较好。const fs require(fs); const data fs.readFileSync(/dev/stdin, utf8).trim().split(/\s/).map(Number); let idx 0; const n data[idx]; const m data[idx]; let ans 0; let prev 0; for (let i 0; i n; i) { const a data[idx]; let need m - a; if (need 0) need 0; if (need prev) ans need - prev; prev need; } console.log(ans);如果环境不支持/dev/stdin就需要改用readline代码会长一些const readline require(readline); const lines []; const rl readline.createInterface({ input: process.stdin }); rl.on(line, line lines.push(line.trim())); rl.on(close, () { const data lines.join( ).split(/\s/).map(Number); // 后续逻辑同上 });JS的Number是64位浮点能安全表示的最大整数是2^53-1这道题的量级完全在安全范围内不需要担心精度。但要小心split(/\s/)这个正则如果有换行和空格混用也能正确切分。还有一个隐蔽的坑用.trim()去掉首尾空白如果输入文件末尾没有换行不trim也不会出错如果输入末尾有一个多余空行不trim会在数组末尾产生一个NaN一旦遍历到NaN所有大小比较都会变成false答案悄悄就错了。4. 高频坑位与AC经验4.1 容易踩的坑这道题代码量很短真正的难度在“读懂题意”和“注意边界”。我把常见的翻车现场整理成了一张速查表。症状原因解决办法答案比预期大很多没有把负数need置为0把已经超高的段也算进需要补的量每个need都做max(0, M - a)处理大样例WA或直接溢出用int存累加值统一改成long long样例都过提交全错输入格式理解错第一行不是N和M而是只有NM要用最大值推看题要确认M是给的还是自己求结果对但某些边界RE用数组存差分长度开到n1但没开n2用滚动变量prev不存差分数组JS版本读入报错或答案异常输入读取方式不兼容或split后产生NaN换成fs/readline兼容写法加trim这里最值得展开说的是“M是从输入给还是自己求”。有些版本不给M而是要求“把每一段都补到所有段中的最大高度”这时候你需要先遍历一遍a找出max再用它当M。但是注意找出max之后那些已经等于max的段need就是0其它段need max - a[i]公式照用。多一次遍历没关系复杂度还是O(N)。如果题面给的是“缺口深度need数组”而不是高度a那你连减法都不用做直接拿need作为目标剖面来算正差分和。4.2 用对拍验证差分结论很多同学看完公式第一反应是这个结论真的对吗我一开始也怀疑过。最稳妥的验证方式不是手推而是写一个暴力算法和快速算法对拍。暴力算法就模拟真实过程每次找到第一个没有达标的段作为左端点向右扩展到遇到已达标段为止把这个区间整体加1操作计数加一直到全部达标。这个暴力代码在小数据下完全正确虽然复杂度很高但用来验证公式够了。我常用的对拍脚本长这样随机生成小数组检查两者结果是否总是一致import random def brute(a, M): a a[:] n len(a) ans 0 while True: i -1 for x in range(n): if a[x] M: i x break if i -1: break j i while j n and a[j] M: j 1 for k in range(i, j): a[k] 1 ans 1 return ans def fast(a, M): ans 0 prev 0 for x in a: need max(0, M - x) if need prev: ans need - prev prev need return ans for _ in range(10000): n random.randint(1, 8) a [random.randint(0, 5) for _ in range(n)] M random.randint(1, 10) if brute(a, M) ! fast(a, M): print(mismatch, a, M, brute(a, M), fast(a, M)) break print(done)跑完一万组随机数据两边结果全都一样这才真正说服自己。我建议你刷这类“结论型”题目的时候都这么干一次十个例子的直觉比背十篇题解都管用。尤其是差分公式这种看起来简单到可疑的东西对拍是消除疑虑最直接的方式。4.3 变体题怎么应对这题最常见的变体有三个你在其他题库里看到“水库”“填坑”“修路”这类字眼多半是同一个内核。第一个变体是目标高度不是统一值而是给定一个target数组每一段要补到它自己的目标值。处理方式完全一样把need[i] max(0, target[i] - a[i])然后套正差分和公式。第二个变体是操作方式变了每次不是“加1”而是可以“把一段区间直接设置成某个高度”。那这题就从差分变成区间合并计数答案是所有“需要补的独立连续段”的数量也就是从左往右扫每当need从0变成正数时答案加1。第三个变体是反向操作比如要从仓库里挖土每段土堆高度超过某个上限时要挖走每次挖一个连续区间问最少挖多少次。这时把M - a[i]改成a[i] - M统计的是负差分绝对值的和正负镜像而已。我自己的习惯是拿到这种场景题先别急着写代码先花两分钟在纸上把题面翻译成数学表达。标出哪些是输入参数哪些是目标函数允许哪些操作限制条件是什么。这一步做完代码十有八九就是几行循环的事。平时刷题多试试用两种语言各写一遍主逻辑再写个暴力脚本对拍这种练习方式比反复背模板管用得多真上了考场思路打开的瞬间你就知道你稳了。