企业官网建设流程全解析

“水库溃坝填补”这个题名，我最早是在华为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[r+1]减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[r+1]加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[r+1]配对，执行一次区间减1，D[l]减1、D[r+1]加1。因为正数和与负数和绝对值相等，这个配对过程一定能持续到所有D清零，总操作次数恰好是正数之和。所以结论是严格成立的。

用前面那个样例来走一遍。初始高度是[1,2,1,3]，M=4，need = [3,2,3,1]。need的差分数组D = [3, -1, 1, -2, -1]（长度为n+1，末尾虚拟一个need[n+1]=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，某个位置高度是0，need就是1e9，N是1e5，差分的正数和可能到1e14级别，int一定会爆。第二，输入用cin搭配ios::sync_with_stdio(false)和cin.tie(nullptr)，在OJ上速度足够，不用自己造快读。第三，prev保存的是上一个位置的need，初始为0，这个0是有含义的：堤坝左边界之外不需要补，所以第一个位置如果需要补3，就相当于相对左侧多出了3次“新开区间”，必须计入答案。

如果你在VS Code里跑这个题，提前把C/C++扩展和编译任务配好，代码写完直接Ctrl+Shift+B编译，别等到考试现场才来折腾环境。这种纯数值题，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如果声明成int，m是long，m - a会自动提升为long，这没问题；但如果你把need也声明成int，m - a的结果被截断成int，大样例直接起飞。所以干脆全部用long。另外注意类的名字必须是Main，这是大多数OJ的硬性要求。Scanner用完关掉是个好习惯，不关其实也行，但写了不亏。

3.3 Python实现

Python代码最简洁，但输入读取这个细节很多人翻车。用input()逐行读在N=1e5时勉强能用，但用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用%d，m和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 容易踩的坑

这道题代码量很短，真正的难度在“读懂题意”和“注意边界”。我把常见的翻车现场整理成了一张速查表。

这里最值得展开说的是“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，统计的是负差分绝对值的和，正负镜像而已。

我自己的习惯是，拿到这种场景题先别急着写代码，先花两分钟在纸上把题面翻译成数学表达。标出哪些是输入参数，哪些是目标函数，允许哪些操作，限制条件是什么。这一步做完，代码十有八九就是几行循环的事。平时刷题多试试用两种语言各写一遍主逻辑，再写个暴力脚本对拍，这种练习方式比反复背模板管用得多，真上了考场，思路打开的瞬间你就知道你稳了。