企业官网建设流程全解析

看到 P7871 的标签是“贪心、差分数组”，难度普及+，熟练的选手心里其实已经有了一个大致剧本：把问题里的区间操作翻译成差分数组上的端点事件，再用贪心把事件配对收尾。题目名字起得花哨，带着东方系列那套“芙兰、姆Q、贤者”的谜题风味，但算法内核并不玄乎——这类题考的就是你有没有把“区间修改”和“最少操作次数”这两个关键词，第一时间接进“差分数组 + 贪心扫描”的框架里。

这篇东西我打算照着自己在洛谷上的做题习惯来写：先讲清楚拿到题该怎么拆，再讲贪心为什么在这里是对的，最后给一套能直接套用的代码模板，顺带把反悔贪心的进阶玩法也说透。适合刚学完差分数组、正在往普及+难度进阶的选手，也适合那些“题解看得懂、自己做就卡壳”的朋友。

1. 拿到题先别急着写，把“区间操作”翻译成“差分事件”

1.1 差分数组为什么能压缩区间操作

先复习一个老生常谈但极其关键的定义。设原数组为a[1..n]，为了方便通常补一个a[0] = 0，差分数组定义为：

d[i] = a[i] - a[i-1]

反过来，原数组可以通过前缀和还原：

a[i] = d[1] + d[2] + ... + d[i]

这个定义本身很简单，但真正值钱的是下面这个对应关系：

• 对原数组执行“区间[l, r]整体加 1”，等价于在差分数组上做两个单点修改：d[l] += 1，d[r+1] -= 1。

为什么？因为区间内部相邻元素的差值没有变化，只有区间的左边界和右边界外侧的差值改变了。你可以把差分数组想象成一本只记录“变化量”的账本：每次转账不需要改动整条流水，只需要在转出方和转入方各记一笔。同理，区间加这种全局耦合的操作，在差分视角下被拆成了两个完全独立的事件。

这个视角很重要，因为“区间操作”往往是一次影响一大片，暴力维护的复杂度是 O(n) 甚至更高；而差分把一次操作压成了 O(1) 的两个点修改。更重要的是，它把“原数组要满足什么条件”这种全局约束，变成了“差分数组上若干个点的约束”。比如“所有元素相等”这个条件，翻译到差分就是d[2..n]全部为 0；而“原数组非负”则等价于差分数组的任意前缀和都非负。很多东西一下子从“看不清全局”变成了“只扫一遍就能判断”。

1.2 目标约束怎么落到差分上

做题的第一步永远是：先把题面里的目标翻译成数学表达。假设题目要你把初始数组start变成目标数组target，那我们关心的其实是一个差值数组：

b[i] = target[i] - start[i]

也就是说，所有操作都是在给这个“缺了多少”的数组做叠加。对这个差值数组再求一次差分，得到：

db[i] = b[i] - b[i-1]

那么问题就变成了：“初始时b全为 0，每次操作可以给b的某个区间整体加 1，问最少多少次能让b变成目标差值数组。”

来一个具体的例子，方便后面推导。假设要从全 0 数组变成：

target = [1, 2, 2, 1, 0]

它的差分数组是：

db[1] = 1 db[2] = 1 db[3] = 0 db[4] = -1 db[5] = -1 db[6] = 0 // 哨兵位置，n+1

正差分之和是1 + 1 = 2。手算一下也确实只需要两次操作：第一次给[1, 4]整体加 1，第二次给[2, 3]整体加 1，就得到了[1, 2, 2, 1, 0]。两次操作，对应的正是两个正差分。这个例子的结论我会在下一节给出严格解释，你先有个直觉：正差分看起来就是“不得不新开操作的地方”。

实际做这类题的时候，我建议在草稿纸上先把db写出来，然后问自己三个问题：正差分能不能对应到一次操作的左端点？负差分能不能对应到右端点？这些端点之间的配对有没有额外限制？如果题面没有额外限制，那恭喜你，这道题已经完成 80% 了。

2. 贪心的出现不是玄学，是“区间开闭”问题的最优性

2.1 每次操作的本质：开一个区间，关一个区间

很多人记结论只记一句“答案等于正差分之和”，但不知道为什么。如果只是背结论，遇到题目稍加变形就会卡住。下面我用一个更直观的模型推导一遍。

把一次区间加操作看成“打开一个区间，然后稍后关闭它”。从左往右扫描差分数组：

• 遇到正差分db[i] = x，意味着这里需要“新开”x个区间，因为差分突然升高了，必须有这么多个区间的左端点落在位置i。
• 遇到负差分db[i] = -y，意味着这里需要“关闭”y个区间，因为差分突然降低了，必须有这么多个区间的右端点落在位置i-1（对应差分数组的位置i减 1）。

整个过程就像拿手头的积木搭一座山：上升的时候必须新拿积木往上叠，下降的时候把手头还没用完的积木撤掉。你手里同时持有的积木数量，恰好就是当前扫描位置的原数组值a[i]。

这个视角和差分数组是同一件事的两种语言：

• 差分数组的语言：d[i] = a[i] - a[i-1]，正差分是“新开”，负差分是“关闭”。
• 积木的语言：原数组a[i]就是当前高度，上升多少就要新拿多少块积木，下降多少就放回去多少块。

“答案等于所有正差分之和”这个结论，本质就是在说：每一块新拿的积木都对应一次区间加操作，而下降时复用之前已经拿在手里的积木，不需要额外操作。

2.2 为什么从左到右扫一遍就能出答案

关键的贪心点在这里：区间没有长度限制，没有数量上限，也没有“某个位置只能作为端点多少次”的约束，所以所有“打开的区间”是完全等价的。

这意味着在从左到右扫描的过程中，我根本不需要记录“具体是哪些区间还开着”，只需要记录“还有多少个区间开着”。遇到下降时，随便关掉任何一个开着的区间效果都一样。这就是无后效性：当前的选择不会影响后续任何决策的最优性。既然没有后效性，贪心就成立了。

用数学语言描述这个扫描过程：

cur = 0 ans = 0 for i in 1..n: delta = target[i] - target[i-1] // 也可以直接算差分 if delta > 0: ans += delta cur += delta

注意cur其实就是target[i]本身，如果目标数组合法（非负），cur永远不为负。整个过程没有任何分支决策，没有优先队列，一个 for 循环就结束了，所以题目难度只是普及+而不是更高。

写到这里顺便提一句：ans = sum(max(0, a[i] - a[i-1]))这个公式在很多题里都出现过，比如经典的“粉刷栅栏”模型。如果你在考场上能快速把它和差分数组对上号，省下来的时间相当可观。

2.3 一个需要警惕的隐藏条件：前缀和不能为负

上面推导有个前提：从全 0 数组开始，只用“区间整体加 1”操作，得到的结果数组必然所有位置都大于等于 0。所以差分数组的任意前缀和（也就是原数组值）必须非负。

如果题目给出的目标数组是[1, -1, 1]这种，那直接用正差分之和就会出错，因为根本不可能从全 0 通过区间加得到负数。遇到这种情况，要回头检查题目是不是允许负数，或者是不是存在两种操作（加和减）。很多新手在这上面翻车，不是因为贪心不会，而是因为做题前没有确认“可达性”。

判断可不可达也很简单：扫描时如果cur出现负数，说明无法达成目标，直接输出-1或者按题面要求处理即可。

3. 落码实战：P7871 这类题的完整编码流程

3.1 读入、差分、扫描三段式

我把这类题的代码组织成固定的三段式，减少思考负担。

第一段，读入原数组a[1..n]，注意下标从 1 开始，并且把a[0]看作 0。

第二段，计算差分。如果题目给的是“初始数组”和“目标数组”，就先把差值数组算出来，再求差值数组的差分。如果题目是从全 0 构造目标，就直接对目标数组求差分。这里的核心公式是：

d[i] = a[i] - a[i-1];

第三段，扫描差分数组，累加所有正差分。可以用一个long long保存答案，因为n最大到 1e5、值域最大到 1e9 时，正差分之和可以达到 1e14 级别，int必炸。

3.2 一个可以直接套用的 C++ 模板

#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; long long a[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } long long ans = 0; for (int i = 1; i <= n; i++) { if (a[i] > a[i - 1]) { ans += a[i] - a[i - 1]; } } cout << ans << '\n'; return 0; }

就这么短。很多人第一次看到这个代码会怀疑：真的就这么简单？对，当题目条件就是“无限制的区间加、求最小次数”时，核心逻辑确实只有这几行。真正需要花时间的是读题和建模，不是写码。

如果题目给的是初始数组s和目标数组t，只需要把循环里的比较对象换成差值：

long long pre = 0, ans = 0; for (int i = 1; i <= n; i++) { long long curVal = t[i] - s[i]; // 当前还需要加多少 long long preVal = t[i - 1] - s[i - 1]; // 上一个位置还需要加多少 if (curVal > preVal) ans += curVal - preVal; }

本质上就是一个通用公式：把所有“上升沿”的幅度加起来。

3.3 常见的考点变形，别被包装迷惑

这类题最常见的变形有这么几种：

我在做题时见过很多题把同样的模型包了一层奇幻背景，什么“贤者施法”“芙兰的弹幕”“谜题石板”，剥开之后还是那个“上升沿求和”的内核。所以别被题面吓住，把“区间操作”和“最少次数”这几个词圈出来，差分数组就该登场了。

4. 进阶：当“贪心”不够用，反悔贪心怎么接住

4.1 什么时候不能再无脑累加

基础模型能直接用，是因为打开的区间完全等价。可一旦题目加了限制，比如“每次操作的区间长度必须恰好为 K”，或者“每个位置作为左端点的次数不超过某个值”，等价性就被打破了。这时候你会发现，扫描到某个位置要关闭区间时，得从若干个还开着的区间里挑一个关，而挑哪个会直接影响后面的可行性。

举个例子。如果区间长度固定为 K，那么一个左端点l只能和右端点r = l + K - 1配对。扫描过程中，正差分产生的“可关闭区间”不再位于一个等待队列里任意挑选，而是有严格的距离限制。如果用基础的“正差分之和”公式，结果必然出错。

这时候就需要更高级的贪心策略：反悔贪心。

4.2 反悔贪心的核心思想

反悔贪心的本质是：先按某种局部最优策略做决定，同时把已经做出的决定放进一个优先队列里。当后续遇到更优的决策时，允许把之前的决定撤销或替换。

用最经典的“汽车加油”问题来理解：沿途每个加油站有不同油量，油箱容量有限，问最少加几次油能到终点。朴素贪心是“没油了才加”，但加哪个站的油呢？正确做法是每经过一个站就把油量放进堆里，没油的时候取堆里最大的那个站加油。这个“取堆顶”的动作就是一种反悔——我并没有在路过时立刻决定加油，而是一直在保留选择权，等必须加油时再选最优的那个。

回到差分模型：如果某些位置不能作为端点，或者配对距离受限，我会把可用的正差分位置存进堆里，遇到需要关闭的负差分位置时，从堆里挑一个“最合适”的来配对。如果后面发现这个配对导致后续无法完成，就再从堆里调整。这个“先推迟决定、遇事再选择、必要时替换”的套路，就是反悔贪心的全部秘密。

4.3 一个方向性的模板思路

下面给一个抽象伪代码，展示这个思路的骨架。假设我们要判断“固定长度 K 的区间加能否达成目标”：

// delta 数组是目标值相对初始值的差分 priority_queue<T> heap; // 堆里存可用的左端点 for (int i = 1; i <= n + 1; i++) { if (delta[i] > 0) { // 这些正差分可以作为左端点，暂时不决定使用，先放入堆 把 i 加入堆中，次数为 delta[i]; } if (delta[i] < 0) { // 需要关闭 -delta[i] 个区间，必须从堆里取出合法的左端点 while (需要关闭的次数 > 0) { 从堆里取一个最合适的左端点 l; if (i - l + 1 != K) { // 长度不匹配，可能需要反悔，调整堆顶或判定不可行 } 配对一次，次数减 1; } } }

这段代码我只给方向，不把它当作标准答案，因为不同题目的限制会导致堆的排序关键字完全不同。但思路是一致的：正差分先“存着”，负差分来的时候再“配对”，配对规则由题目限制决定，必要时用堆实现反悔。

写这种题最容易犯的错是“过度设计”。很多题目其实用不到反悔贪心——基础贪心已经足够，只是你被题面吓住，硬给自己加难度。我的建议是先把最简单的情况模拟一遍，确认是否真的存在“两个选择效果不等价”的情况，再考虑上堆。

5. 我踩过的坑，和给后来者的三条建议

5.1 数据范围、long long 与初始化

第一个坑就是int溢出。差分数组的正差分之和上限是n * max(a)，当n = 1e5、max(a) = 1e9时，答案是1e14，int直接爆掉。洛谷这类普及+题很容易把数据范围顶到 1e5 和 1e9，所以读入数组、算答案、维护当前扫描值，全部用long long，别心存侥幸。

第二个坑是边界。我第一次写这类题时，经常忘记把a[0]初始化为 0。如果数组是 1-indexed，a[0]默认是全局变量还好；如果写在函数里忘了初始化，或者题目从 0-indexed 读入，循环里a[i] - a[i-1]就会在i = 0那一下出错。老老实实把a[0] = 0写成显式赋值，或者循环从 1 开始，都能避开。

第三个坑是差分数组的哨兵位置。目标数组的差分有一个db[n+1] = -a[n]（因为a[n+1] = 0），这个位置虽然通常不会被扫描，但在推导可行性时会用到。特别是当你把“区间操作”翻译成“d[l] += 1, d[r+1] -= 1”时，r+1可能等于n+1，这个哨兵必须存在，否则模型不完整。

5.2 别跳过推导，直接在考场套公式

我见过不少选手，看到“区间加”就写上sum(max(0, a[i] - a[i-1]))，结果题目一问“能否用恰好 K 次操作完成”就懵了。

原因很简单：他们不知道公式是怎么来的，所以无法判断公式还能不能继续用。比如“恰好 K 次”这个问题，如果最小次数是m，而K > m，是否可行取决于能否在保持最终结果不变的情况下增加操作次数。通常的做法是找一个区间，对它加两次、再对它的子区间减一次——如果题目不允许减操作，那就得看能否通过“长度 1 的区间”来凑。这些细节完全依赖题面，不可能靠一个公式通吃。

所以我强烈建议，平时练题时把“正差分之和”这个结论从头推导一遍，尤其是用本章第二节的“开区间/关区间”模型。一旦你理解了每一块正差分对应的是一次新操作，你就能灵活应对各种变体。

5.3 如何训练这类“标签识别”能力

最后聊聊能力怎么练。每次看到一道题，先在草稿纸上写下三个信息：题面里的操作是什么、要求的最优目标是什么、数据范围是什么。然后问自己：操作能不能被差分数组拆成端点事件？如果能，答案大概率依赖某种扫描或贪心。

给自己定一个小目标：连续做 10 道“区间加 + 最小操作次数”的题，不求难度高，但求每道都写出“差分推导 + 扫描代码”完整过程。做完之后你会发现，这类题在洛谷上就像一个模子刻出来的——背景换得再花哨，内核纹丝不动。到那时，P7871 在你眼里就不再是“芙兰、姆Q、贤者”的谜题，而是明明白白的“差分数组 + 贪心扫描”模板题。

我个人更推荐从“积木搭高度”的视角去理解这个模型，它会让你在面对“为什么答案等于上升沿之和”时有一种直觉：所有上升都是必须付出的成本，所有下降都是免费的红利。想通了这一点，贪心就不再是背诵的结论，而是真正长在脑子里的思维方式。