企业官网建设流程全解析

最近在模拟赛里做到一道叫《楼房搭建》（building）的题，源文件名很直白，但题面并不是"给你几个数模拟盖楼"那么简单。它把区间操作、差分、贪心三件事揉在一起，考场上不少人是"看着样例能过，改个数据就懵"。我在赛后把整个思路重新推了一遍，顺便把同族的变式也整理了，写出来给准备省选的朋友做个参考。

下面按最常见的版本展开：有 n 栋楼，初始高度都为 0，给定每栋楼的目标高度 h_i，每次操作可以选一个连续区间 [l, r]，把区间内所有楼房同时加高 1 层，问最少操作多少次，才能让每栋楼高度恰好等于目标高度，且过程中任意楼房高度不为负。如果你在别的 OJ 上看到的版本多了"可减"或"初始高度不为 0"，不用慌，第 2 节会补上通用化的结论。

1. 拆题：先把"盖楼"翻译成差分

1.1 这题到底在问什么

把目标高度数组 h 画出来，它其实就是一条从左到右起伏的轮廓线。每次"区间加 1"，相当于在某一段轮廓线上方再铺一层"土"。

换个角度理解：所有楼房都是一层一层从下往上盖的。每一层水平方向看过去，就是若干个互不相交的连续区间。比如目标高度是 [2, 0, 3]，第一层要盖的区间是 [1,1] 和 [3,3]，第二层同样，第三层只需要盖 [3,3]。于是问题变成：拼出整张轮廓线，最少需要多少个这样的"水平层段"。

从左往右扫目标高度，很容易发现规律：当 h_i 比 h_{i-1} 高时，说明这里必须"新开始"若干层；当 h_i 比 h_{i-1} 低时，只是某些层在这里"结束"，并不需要额外的操作。所以答案只和"上升量"有关。

1.2 一步到位的公式

记 h_0 = 0，最少操作次数为：

ans = Σ_{i=1}^{n} max(0, h_i - h_{i-1})

这个公式又常写成差分形式。定义差分数组 d_i = h_i - h_{i-1}，则答案就是所有正 d_i 的和。

为什么必须是正的增量？因为每一层从左边开始向右延伸时，只有在高度上升的位置才会产生"这个层段从这里开始"的需求。下降的位置只是让之前的某些层段结束，不需要额外开新层段。

例如 h = [2, 0, 3]：

总数 = 2 + 3 = 5。实际操作：第 1 层盖 [1,1] 与 [3,3]，第 2 层盖 [1,1] 与 [3,3]，第 3 层盖 [3,3]，正好 5 次。

1.3 为什么这个贪心是对的

先看下界：如果 h_i > h_{i-1}，多出来的 h_i - h_{i-1} 层在位置 i 必须从某个区间的左端点开始，否则位置 i-1 早就达到这个高度，而位置 i 却不够。每一层段的起点对应一次操作，所以上升量之和就是操作次数的下界。

再看上界：按照从左到右的顺序，每遇到一次上升，就立刻新开足够多的区间，左端点放在当前位置；右端点先不固定，等到后面高度下降时再关闭对应数量的区间。这种构造一定能达到目标高度，而且操作次数恰好等于上升量之和。

所以这个贪心不仅正确，而且实现起来只有一层循环。

提示：这个结论同样适用于"每栋楼至少要达到某个高度"的版本。区别只是把"恰好等于"改成"覆盖住需求"，答案不变，因为多盖的楼层没有意义，最优解总是贴着目标高度走。

2. 通用化：初始高度不同，允许正负调整

2.1 引入差异序列 c

模拟赛里有时候不会把初始高度全给成 0，而是给一个初始数组 a 和一个目标数组 b。这时候真正需要处理的是净增量：

c_i = b_i - a_i

如果题目规定只能加高，那么必须满足所有 c_i ≥ 0。此时答案仍然是：

ans = Σ_{i=1}^{n} max(0, c_i - c_{i-1})

其中 c_0 = 0。这等价于把"从 0 盖到 c_i"看成一个新问题。

如果题目允许加高也允许拆除，也就是每次操作可以选区间加 1，也可以选区间减 1，那么结论会更漂亮：答案等于差分数组的正部分之和。

设 c_0 = c_{n+1} = 0，构造差分：

e_i = c_i - c_{i-1}

最少操作次数 = Σ_{i=1}^{n+1} max(0, e_i) = -Σ_{i=1}^{n+1} min(0, e_i) = Σ |e_i| / 2

为什么这次连下降量也要算？因为拆除不能凭空发生，一次"区间减 1"在差分里是在左端点产生一个 -1，在右端点后一位产生一个 +1。要让差分数组全部归零，正负必须配对，而每一对配对就是一次操作，所以至少需要正差分总量这么多次操作。

2.2 一个完整例子

初始 a = [1, 3, 2]，目标 b = [2, 0, 4]。

净增量 c = [1, -3, 2]

差分 e_1 = 1 - 0 = 1 e_2 = -3 - 1 = -4 e_3 = 2 - (-3) = 5 e_4 = 0 - 2 = -2

正差分之和 = 1 + 5 = 6，所以答案是 6。这 6 次操作可以这样构造：

• 对区间 [1,3] 加 1 一次：高度从 [1,3,2] 变成 [2,4,3]
• 对区间 [2,2] 减 1 四次：高度从 [2,4,3] 变成 [2,0,3]
• 对区间 [3,3] 加 1 一次：高度从 [2,0,3] 变成 [2,0,4]

总共 6 次，过程中所有楼高非负，完全合法。

这个例子想说明一件事：允许拆除的时候，不一定非得严格地一层一层盖，中间某栋楼可以先被抬起来，之后再拆掉。差分模型把这种"超调再恢复"的过程也统一处理了。

2.3 什么时候配对会不合法

用差分配对时，隐含要求是"左端点在右端点之前"。比如 e_3 = +5 出现在位置 3，e_2 = -4 出现在位置 2，如果不加限制地让它们配对，就会得到一个右端点在左端点左边的非法区间，这种方案不可行。

解决办法是规定配对顺序：正差分对应"区间加 1"的左端，所以它必须匹配到它右侧的某个负差分；反过来，负差分在左、正差分在右，可以理解为"区间减 1"。在实现里，这通常用一个栈来维护尚未关闭的正差分位置，从左到右扫描，遇到负数时优先从栈里取最近的候选来配对。

如果题目还规定了"每栋楼任何时刻不能超过目标高度""区间长度不能超过 L"这类限制，配对就不能只看左右顺序了，这时候才会轮到堆出场。

3. 哪些变式必须用堆，以及怎么用

3.1 不定长区间加"长度限制"

有些版本会加一个很现实的条件：一次操作只能覆盖长度不超过 L 的连续段。比如脚手架长度受限，刷墙工人一次最多刷 L 栋楼。

这时候"把区间右端点一直拖到下降处"的策略不成立了，因为右端点和左端点的距离可能超过 L。正确贪心是：从左到右扫描，维护当前正在被覆盖的层数 cur。如果当前位置的需求 h_i 大于 cur，就必须新开 h_i - cur 个区间，每个区间从 i 开始，右端点尽量向右延伸到 i + L - 1（不能越界）。用差分数组记录每个位置有多少区间同时结束，就能在 O(n) 内完成。

这种写法不需要堆，因为新区间的右端点只有"尽量远"这一种最优选择，不需要比较多个候选。核心思想是：能延伸多远就延伸多远，反正左端点已经固定，右端点越远对后面的覆盖只会更有利。

3.2 给定一批固定区间，求最少选几个

这是另一类更常见的"楼房"题：有 m 个已经给定的施工区间，每个区间使用一次，会给区间内所有楼加高一层，问最少选多少个区间，才能让每栋楼被覆盖次数至少达到 h_i。

这种题才真正需要堆。贪心策略是：

• 所有区间按左端点从小到大排序
• 从左到右处理每个位置 i
• 把所有左端点 ≤ i 的区间加入一个大根堆，堆里按照区间右端点排序
• 弹出所有右端点 < i 的区间（已经无法覆盖当前位置）
• 如果当前覆盖次数不够 h_i，就从堆顶取右端点最大的区间使用，每用一个覆盖计数加 1，直到满足需求或堆空

为什么取右端点最大的？因为对于当前位置左边的区间，右端点越大，就意味着它还能继续覆盖后边更多的位置。同样的代价，当然选剩余覆盖能力最强的区间。

核心代码如下：

#include <bits/stdc++.h> using namespace std; struct Seg { int l, r; bool operator<(const Seg& other) const { return l < other.l; } }; int main() { int n, m; cin >> n >> m; vector<long long> h(n + 2); for (int i = 1; i <= n; i++) cin >> h[i]; vector<Seg> seg(m); for (int i = 0; i < m; i++) { cin >> seg[i].l >> seg[i].r; } sort(seg.begin(), seg.end()); vector<long long> add(n + 3, 0); priority_queue<int> pq; // 大根堆，存右端点 int ptr = 0; long long cover = 0, ans = 0; for (int i = 1; i <= n; i++) { while (ptr < m && seg[ptr].l <= i) { pq.push(seg[ptr].r); ptr++; } cover += add[i]; while (!pq.empty() && pq.top() < i) pq.pop(); long long need = h[i] - cover; while (need > 0 && !pq.empty()) { int r = pq.top(); pq.pop(); ans++; cover++; add[r + 1]--; need--; } if (need > 0) { cout << -1 << '\n'; return 0; } } cout << ans << '\n'; return 0; }

这个版本要求区间使用次数不限，每个区间最多用一次。如果允许同一个区间重复使用，就在弹出后重新入堆，并做好次数限制，逻辑类似。

3.3 怎么判断自己的题该用哪种算法

我整理了一个简单的对照表，做题前先对号入座：

很多同学一看"省选模拟"就觉得必须写堆，结果把简单题做复杂了。其实基础版是一个 O(n) 扫描，连排序都不用。先看数据范围和操作自由度，再决定优化方向。

4. 代码实现与调试心得

4.1 基础版参考代码

以初始全 0、目标数组 h、只能加高为例：

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

如果题目允许区间加也允许区间减，那就把 h 数组换成差异数组 c，再对差分数组统计正项和：

vector<long long> c(n + 2); for (int i = 1; i <= n; i++) c[i] = b[i] - a[i]; long long ans = 0; for (int i = 1; i <= n + 1; i++) { long long d = c[i] - c[i - 1]; if (d > 0) ans += d; }

注意 c[0] 和 c[n + 1] 都要定义为 0，循环到 n + 1 是必须的，不然最后一个差分项会漏掉。

4.2 最容易踩的坑

先说最经典的：答案要开 long long。n 到 2e5，高度到 1e9，正增量之和完全可能到 1e14 量级，int 必炸。很多选手公式写对了，最后挂在输出类型上，非常可惜。

其次是差分数组的开法。无论用哪种模型，只要涉及差分，数组至少开 n + 3。原因是区间右端点在 n 的时候，对应的差分位置是 r + 1 = n + 1，循环里还可能访问到 n + 2。开小了会出现随机越界，本地可能不报，放到 OJ 上就是一堆莫名其妙的 RE。

第三是堆贪心版本里"先弹失效区间"的顺序。不能在取堆顶之后才判断右端点是否小于当前位置，因为堆顶只是右端点最大的，不代表所有堆内区间都有效。必须先循环弹出所有 r < i 的区间，再尝试取区间使用。

第四，也是最容易被忽略的：一定要分清题面写的是"恰好等于目标高度"还是"至少达到目标高度"。基础版对"恰好"成立，堆贪心版对"至少"成立。有的题目数据弱，两种写法都能过样例，但换一组数据就全错。我模拟赛里就被这个坑过，审题花了二十分钟，最后改一行才 AC。

4.3 对拍：用暴力给自己兜底

这类题的正确性容易想当然，我强烈建议写一个暴力程序对拍。

暴力思路很简单：n 很小的时候，直接 DFS 枚举所有可能的区间操作，每次选一个区间加 1，直到所有楼高度达到目标，记录最小步数。也可以用 BFS 按层搜索，状态压缩成高度数组。

对拍脚本的流程是：

• 随机生成 n，范围 1 到 8
• 随机生成 h_i，范围 0 到 5
• 跑暴力程序，得到答案 ans_brute
• 跑贪心程序，得到答案 ans_fast
• 两者不一致就输出当前数据和两个答案

我一般会跑 1 万组随机数据。如果对拍全部通过，基本可以放心提交。这个方法看起来笨，但对这类"区间 + 差分"的题特别管用，因为暴力的状态空间很小，而贪心的边界情况很多。

5. 从这道题能带走什么

先说结论：遇到任何"区间统一加/减"的题，第一步永远是写差分。区间操作在差分数组上只会影响两个点，这个转换能把问题维度从"区间"降到"点"，后续无论是贪心还是数据结构优化都会清晰很多。

第二步是判断操作自由度。如果可以任意选择区间，且没有长度限制，多半是 O(n) 扫描；如果可用区间是离散给定的，或者区间长度受限且需要动态比较候选，才需要堆。很多省选模拟题其实是在考你"能不能忍住不写堆"。

第三步是别忽视合法性约束。差分配对只保证数量最少，不保证每栋楼在操作过程中不违反高度限制。遇到这种额外限制，先从栈/堆维护合法性的角度想一想，而不是直接套公式。

我在实际比赛中体会最深的一点是：这种看起来"名字很工程"的题，往往核心数学模型并不复杂。复杂的是人容易先入为主，觉得省选模拟必出数据结构。先把题意翻译成数学语言，再决定用什么工具，比一开始就抱着线段树和堆去找题眼要靠谱得多。

最后分享一个小技巧：比赛时拿到题，先在草稿纸上把题面里的操作翻译成符号语言，比如"区间 +1 = 左差分 +1、右端点后一位 -1"，翻译完再去看数据范围。我自己的经验是，这类翻译做完，至少一半的思路已经出来了。剩下的，就是老老实实写暴力、对拍、补边界。希望这篇复盘能帮你在下一次模拟赛里少踩几个坑。