楼房搭建问题：贪心差分建模与O(n)求解

1. 题目拆解与核心考点省选模拟题里出现“楼房搭建”这种名字乍一看像是签到题或大模拟但实际做过几套省选模拟的都知道这种题名越朴素内里往往越考验建模能力。这道题的核心不是“盖楼”本身而是如何把一个看似无序的序列操作问题转化为一个能用贪心或差分维护解决的数学问题。1.1 题目形态与第一眼判断假设题面给出的是一排连续的地块编号 1 到 n每个地块上最终要建成高度为 h[i] 的楼房。初始所有地块都是平地高度为 0。允许的操作是一次选择某个地块把它加高 1 个单位或者选择相邻的两个地块同时把它们各加高 1 个单位。目标是用最少的操作次数使得所有地块的高度恰好达到目标序列 h。为什么要用“最少操作次数”而不是别的统计量因为这类覆盖型操作问题在竞赛里最经典的转化就是“把每个操作看成一个区间增量”然后通过差分数组来统计每个位置实际被覆盖了多少次。楼房搭建这道题单点加高相当于长度为 1 的操作相邻两个地块同时加高相当于长度为 2 的操作。我们可以把问题重新描述为有多少对相邻位置被共同操作了 x 次、有多少个单点位置被单独操作了 y 次使得最终每个位置的覆盖量等于目标高度 h[i]且让 x 和 y 的总和最小。这个第一眼判断很重要。很多人拿到题直接想贪心模拟“从左往右扫能用区间操作就用区间操作”但这种直觉并不总是正确的尤其是当 n 很大、h[i] 又存在高低起伏时。先把它抽象成“覆盖次数分配”的问题才能避免在错误的方向上浪费大量时间。1.2 难度评估与常见卡点从省选模拟的定位来看这道题大概率是“中等偏易”或“中等”的档位因为它不会像数据结构题那样需要复杂的树套树或平衡树但它对思维转化的要求高于平均水平。常见的卡点有三个一是死磕“从左到右贪心”的方向。如果 h 序列是单调递增的从左到右贪心非常自然可一旦目标序列出现高低起伏比如 h {3, 1, 3}单纯从左往右贪心就会发现中间的凹陷无法优雅处理——区间操作会“跨过”凹陷把本来不需要加高的位置也加高了。二是忽略边界条件。n 只有 1 时区间操作不存在答案显然就是 h[1]n 为 2 时情况也变得非常简单无非是比较单点操作和区间操作谁更优。但很多人写代码时不处理这几种极小规模的情况结果在数据里挂掉。三是建模后不会收尾。把问题转化为数学表达式不难但如何在 O(n) 时间内求出最小操作数需要进一步观察贪心性质。我见过不少选手在“式子列出来了但不会求解”这一步卡住说明他们对差分数组和贪心配合的套路还不够熟练。整体来说这道题的训练价值在于它强迫你从“操作过程”的视角跳出来切换到“统计覆盖”的视角这是很多序列构造类题目的共性思路。2. 从过程模拟到数学建模拿到这类题第一步永远是尝试写出最朴素的模拟过程然后思考如何优化。朴素模拟是这样的从左往右扫描如果当前高度还达不到目标就尽量用“双位置操作”把当前位和下一个位置一起抬高如果下一个位置已经达标就只用单点操作补足当前位。这个朴素模拟在 h {2, 3, 2} 时表现如何从左往右看位置 1需要 2 次操作若都用双位置操作位置 1 和位置 2 各加 2此时位置 2 达到 2还需要 1 次才能到 3位置 3 需要 2但目前是 0。继续用双位置操作把位置 2、3 各加 1此时位置 2 到 3位置 3 到 1还差 1。最后位置 3 用单点操作补 1。总操作数2 1 1 4。这个结果是对的但朴素模拟的过程很难推广到复杂序列因为你不知道什么时候该保留双位置操作的“额度”给更后面用。2.1 记录“剩余覆盖额度”的数组换个更聪明的思路不模拟操作过程而是记录“已经有多少次双位置操作从左边延伸到了当前位置”。设 f[i] 为“第 i 个位置和第 i1 个位置共同被加高的次数”也就是长度为 2 的区间操作在边界 i 上的数量。那么每个位置 i 的总覆盖次数可以写成c[i] f[i-1] f[i] s[i]其中 s[i] 是该位置单点操作的次数f[i-1] 是它与左边邻居共享的操作数f[i] 是它与右边邻居共享的操作数。注意这里 f[0] 和 f[n] 都是不存在的边界设为 0。这个式子很直观一个位置要么被左边的双位置操作覆盖要么被右边的双位置操作覆盖要么被自己的单点操作覆盖三条来源加在一起恰好等于目标高度 h[i]。总操作次数就是 sum(f) sum(s)。目标是让这个总和最小同时满足对每个 i 都有 f[i] 0 且 s[i] 0。2.2 为什么 f 的选取是关键一旦写出这个等式你会发现问题的自由度其实只在于 f 数组怎么选。因为 s[i] 可以被 h[i] - f[i-1] - f[i] 唯一确定只要这个值非负。于是问题进一步化为找到非负整数数组 f[1..n-1]使得对任意 i都有 f[i-1] f[i] h[i]并最小化 sum(f) sum(h[i] - f[i-1] - f[i])。仔细算一下这个目标函数sum(f) sum(h) - sum(f[i-1] f[i])其中 sum(f) 是 f[1] 到 f[n-1] 的和sum(f[i-1] f[i]) 对 i 从 1 到 n 求和展开后是 f[0] 2*(f[1] ... f[n-2]) f[n-1]由于 f[0]f[n]0这恰好是 2*sum(f)。目标函数简化为 sum(h) - sum(f)。这就非常有意思了总操作数等于目标高度的总和减去区间操作的总次数。换句话说每使用一次双位置操作就比单点操作省 1 次操作。那么问题变成了在满足约束 f[i-1] f[i] h[i] 的前提下最大化 sum(f)。2.3 贪心求最大 f 的思路最大化 sum(f) 是一个经典的“选不相交或部分相交区间”的变种问题。因为 f[i] 只影响位置 i 和 i1 的约束本质上是说相邻两个 f 值之和不能超过某个上限。这种约束下贪心通常可以从左往右做每个位置 i 在满足当前约束的前提下尽量把 f[i] 设大因为它既能提升总和又不会对前面的位置产生额外负担。为什么“尽量设大”不会影响后面的可行性因为 f[i] 越大位置 i1 的可用额度 h[i1] - f[i] 就越小看起来可能限制 f[i1] 的取值。但关键在于f[i1] 本身也在目标函数中贡献正向收益而 f[i] 的收益是等价的。我们要做的不是在“当前获益”和“未来获益”之间取舍而是确保每个位置的高度约束不被突破。贪心的正确性可以用交换论证证明如果某个最优解中 f[i] 没有取到在当前约束下能取到的最大值那么把它增大到最大值同时适当调整后续 f 值总能得到不更差的结果。这个推导过程建议第一次接触的选手在纸上多推几遍因为“最小化操作数等于最大化区间操作数”这个结论是整道题的核心突破口。3. 实操推导从 O(n²) 到 O(n) 的逐步收敛如果说上一节是“建模”这一节就是“求解”。模型建出来了但直接枚举 f 数组是不可能的n 可以到几十万f 的取值更是天量。我们需要进一步观察约束结构找到一个线性的贪心流程。3.1 从左到右的贪心递推设 g[i] 表示处理完前 i 个位置后f[i] 的取值。我们从 i 1 开始此时约束条件只有 f[1] h[1]因为 f[0] 0。为了让总收益最大化显然先把 f[1] 设成 h[1] 是最优的此时 s[1] 0。接着处理位置 2。现在约束是 f[1] f[2] h[2]而 f[1] 已经确定为 h[1]。那么 f[2] 能取的最大值是 max(0, h[2] - h[1])。注意这里是“最大值”因为在贪心策略下我们希望在满足约束的前提下让 f[2] 尽量大。但这里立刻就出现了一个问题如果 f[2] 取这个最大值位置 2 本身的约束已经拉满但位置 3 的约束还没检查。这没问题因为位置 3 的检查在下一步进行而我们始终保证的是“当前已经确定的所有 f 都满足它们对应的约束”。再处理位置 3。约束是 f[2] f[3] h[3]f[2] 已确定所以 f[3] 的最大可取值为 max(0, h[3] - f[2])。把这个过程一直推进到 i n-1最后检查位置 n 的约束 f[n-1] f[n] h[n]f[n] 0如果成立说明我们得到了一组可行解如果不成立说明题目无解——但本题保证有解所以这一步只是验证。3.2 用差分思想理解贪心过程上述递推看起来很简单但代码实现时很容易踩坑。我们把它改写成差分的形式更清晰令 d[i] h[i] - h[i-1]并约定 h[0] 0。从左到右扫描时f[i] 的实际取值其实就是在累计“当前高度差被双位置操作吸收之后剩余的部分”。举个例子h {2, 5, 3, 4, 1}位置 1f[1] 2位置 2约束 h[2] 5f[1] f[2] 5f[2] 最大取 3位置 3约束 h[3] 3f[2] f[3] 3f[3] 最大取 0位置 4约束 h[4] 4f[3] f[4] 4f[4] 最大取 4位置 5最后检查 4 0 1 不成立说明我们的贪心选择导致位置 5 超限。看到问题了吗前面“最大可取”的贪心在位置 4 时取了 f[4] 4但 h[5] 1 根本接不住这个值。这说明从左到右“每步取最大”的简单贪心是错的因为它只考虑了当前位置的约束没有给未来留余地。正确做法需要一种“带有后悔机制”的贪心或者换一个更全局的视角。3.3 最大覆盖数的线性求法既然每步贪心不行那怎么求最大 sum(f) 呢这里需要引进一个很关键的观察f[i] 和 f[i-1] 之和被 h[i] 限制这意味着所有位置的高度总和给双位置操作提供了一个“全局容量”。但从局部看f[i] 的取值又必须被左右两个高度“夹住”。我们可以把每个位置 i 视为一个分隔点左边高度 h[i-1] 能支撑的最大 f[i-1] 是 h[i-1]右边高度 h[i1] 能支撑的最大 f[i] 是 h[i1]且 f[i-1] f[i] 不得超过 h[i]。这是一个典型的“匹配”问题可以在 O(n) 内用类似“维护剩余额度”的方法解决。具体做法从左往右扫描维护变量 rest表示当前这个位置在处理完左边的覆盖之后还能接受多少来自右边的覆盖。初始化 rest h[1]。对于每个 i 从 1 到 n-1令 take min(rest, h[i1])表示从右往左延伸进当前区间的双位置操作数量。这个 take 就是 f[i] 的取值。然后更新 rest位置 i1 的总高度 h[i1] 已经被 take 消耗了剩余可以接受右边覆盖的额度为 h[i1] - take。即 rest h[i1] - take。但要注意位置 i1 的剩余额度不仅来自“未被右边双位置覆盖的部分”还要考虑它自己能否支撑 f[i1]。这个递推把所有位置扫完后如果最后 rest 0 说明所有覆盖都恰好闭合若 rest 剩下正值说明最后一块被单点覆盖补齐若出现负值说明无解。用这个方法重新算上面的例子初始 rest 2i1take min(2, 5) 2f[1] 2rest 5 - 2 3i2take min(3, 3) 3f[2] 3rest 3 - 3 0i3take min(0, 4) 0f[3] 0rest 4 - 0 4i4take min(4, 1) 1f[4] 1rest 1 - 1 0最终 sum(f) 2 3 0 1 6sum(h) 2 5 3 4 1 15答案 15 - 6 9。对比之前的错误贪心这个结果才是真正满足所有约束的。为什么 min(rest, h[i1]) 这个操作是关键因为 rest 表示“左边允许延伸过来的覆盖额度”h[i1] 表示“右边位置能承受的覆盖上限”两者取小的部分就是能够落在边界 i 上的双位置操作数。这本质上是把一个“相邻约束”问题转化成了“相邻传递”问题每次传递都保证不会突破任何一边的限制。这种“维护剩余额度 取 min”的套路在很多序列操作的题目里都通用。它比朴素的逐项贪心多了一个核心思想当前决策要同时考虑左右两边的容量而不是只想着让当前值尽量大。一旦想通这一点代码就可以写得非常短。4. 代码实现与边界细节思路梳理清楚之后代码实现反而是最不需要动脑子的部分但也是最容易出 bug 的部分。我用类 C 的语法展示核心流程并标注出几个容易写错的地方。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long h(n 1), f(n, 0); long long ans 0; for (int i 1; i n; i) { cin h[i]; ans h[i]; // 累加总高度 } long long rest h[1]; for (int i 1; i n; i) { long long take min(rest, h[i 1]); f[i] take; ans - take; // 每使用一次双位置操作总操作数就减 1 rest h[i 1] - take; } cout ans endl; return 0; }这段代码看起来简单但要理解两个细节第一为什么 ans 初始化为 sum(h)因为如果全部用单点操作总操作数就是所有高度的总和。每次取一个双位置操作相对于两个单点操作来说节省了一次所以直接减掉 take。第二为什么 rest 的更新是 h[i1] - take 而不是其他形式因为 h[i1] 在本次迭代中已经被 take 个双位置操作覆盖了剩下的高度额度要留给下一次迭代时从 i1 延伸到 i2 的双位置操作使用。4.1 边界情况处理n 1 时循环根本不会执行rest h[1]ans h[1] - 0 h[1]答案是 h[1]正确。n 2 时i 1take min(h[1], h[2])ans h[1] h[2] - min(h[1], h[2]) max(h[1], h[2])这完全符合直觉两个位置搭建时先共同加高 min 次再把高出来的部分单独加高总次数恰好等于最大值。数据范围上h 可能到 1e9n 可能到 1e6sum(h) 可能超出 int 范围所以必须用 long long。很多选手在这里挂掉因为只开了 int导致大规模数据下答案溢出变成负数WA 得莫名其妙。4.2 无解情况的判断与题目承诺虽然在多数题面中这种搭建问题天然有解因为单点操作永远可以补齐但有时候出题人会加限制比如“双位置操作最多使用 k 次”那就不能用简单的减法了。更常见的变体是把操作改成“选择位置 i将其加高 1或者选择位置 i 和 i1同时加高 1”此时单点操作永远存在题目必然有解。如果你拿到的题面描述了不同的操作方式一定要先判断操作下界。比如某变体规定“只能选连续三个位置同时加高”那所有 h 都不能被某个数整除就存在无解的情况。遇到这种题建议在实现时加一个检查扫描结束后判断 rest 是否等于 0若不等于 0 且题目要求恰好达成就要输出无解标记但若题目保证有解这个检查可以省略。5. 常见错误与调试实录这道题我在给训练队学生讲解时收集了不少典型的错误这里挑几个最有代表性的分享。5.1 全局贪心导致的隐蔽错误有个 A 同学写出了这样的核心逻辑long long sum 0; for (int i 1; i n; i) { long long tmp min(h[i], h[i 1]); sum tmp; h[i] - tmp; h[i 1] - tmp; }这段代码看起来像是“每次把相邻两块能叠加的部分都叠加掉”但它的问题非常隐蔽当 h {10, 1, 10} 时i1 时 tmp 1把位置 1 变成 9、位置 2 变成 0i2 时 tmp 0。sum 1但正确答案是多少用我们前面的算法rest 10i1 时 take min(10, 1) 1rest 0i2 时 take min(0, 10) 0。sum(f) 1答案 21 - 1 20。看起来 A 同学的答案也是 20难道没问题换一组数据 h {5, 4, 5}。A 同学i1 时 tmp 4h 变为 {1, 0, 5}i2 时 tmp 0sum 4答案 14 - 4 10。但我们算法的 take 序列是rest 5i1 时 take min(5, 4) 4rest 0i2 时 take min(0, 5) 0也是 4。这里碰巧一致。继续试 h {3, 5, 4}。A 同学i1 时 tmp 3h 变为 {0, 2, 4}i2 时 tmp 2sum 5答案 12 - 5 7。我们的算法rest 3i1 时 take min(3, 5) 3rest 2i2 时 take min(2, 4) 2rest 2。sum(f) 5答案同样是 7。那 A 同学的写法真的总是等价吗再试 h {4, 7, 3, 5}。A 同学i1 时 tmp 4h 变为 {0, 3, 3, 5}i2 时 tmp 3h 变为 {0, 0, 0, 5}i3 时 tmp 0sum 7答案 19 - 7 12。我们的算法rest 4i1 时 take min(4, 7) 4rest 3i2 时 take min(3, 3) 3rest 0i3 时 take min(0, 5) 0rest 5。sum(f) 7答案 12。看起来还真是等价的这里要澄清一个容易混淆的点A 同学写的贪心是“从左到右每次用尽当前相邻重叠”它本质上和我们的“维护 rest 取 min”在满足相邻约束时是等价的因为每次取 min(h[i], h[i1]) 其实已经隐含了一个条件——h[i] 在之前的迭代中已经被削减到不超过 rest 了。但这种写法的前提是 h 数组可以直接修改且不会出现负数。若出现负数说明操作过度此时必须立刻止损。所以我建议还是用 rest 的写法因为它不需要修改原数组逻辑更清晰也不容易在数据量大时出现混乱。5.2 long long 与溢出问题这是最没技术含量但最常见的问题。换句话说九成以上的 WA 出在 int 溢出上。h 的取值一旦超过 1e5n 超过 1e5sum(h) 就能达到 1e10 量级int 完全扛不住。遇到这种题养成习惯所有累加变量一律开 long long不要心存侥幸。5.3 输出答案的语义搞混还有一类错误是把 ans 直接输出成 sum(f)。sum(f) 是双位置操作的次数不是总操作数。总操作数必须用 sum(h) - sum(f) 计算。如果你发现自己的答案“只差一点”或者“比标准答案小”优先检查是不是漏了单点操作的部分。5.4 调试技巧一个很实用的调试方法随机生成小规模数据写一个暴力枚举程序验证。暴力方法很直接BFS 搜索所有操作序列因为操作顺序不影响最终结果所以本质上是在枚举每个位置有多少单点操作、每个相邻边界有多少双位置操作。然后用暴力结果和贪心结果对比。随机测个几千组基本能确认算法的正确性。6. 变式拓展与思维迁移这道题的核心价值在于可迁移性。如果出题人把操作改成“选择连续 k 个位置同时加高 1”思路会怎么变化呢我简单说说。6.1 连续 k 个位置同时加高操作变成区间长度固定为 k 的增量那么每个位置被覆盖的次数由它左边 k-1 个边界的区间操作共同决定。设 f[i] 表示从 i 开始的区间操作次数作用于 i 到 ik-1那么位置 i 的覆盖次数可以表示为从 i-k1 到 i 的所有区间覆盖之和。这时候 f 数组的约束不仅是“相邻两个之和不能超过 h”而是“长度为 k 的滑动窗口和不能超过 h[i]”。最大化所有 f 的总和等价于在每个窗口和约束下尽量多放区间操作。这个问题用贪心 差分也能求但麻烦一些。需要从左往右维护一个延迟标记记录当前窗口内已经累计的覆盖数然后每个位置把覆盖数压到上限以内。本质还是“维护剩余额度”的思想只是窗口从 2 变成 k。6.2 操作类型为“抬高较低位置”还有一类变体规定操作是选择一栋楼将它高度增加 1代价是 1或者选择两栋相邻且高度相同的楼同时增加 1代价是 1。这等价于我们的原题加上“必须相等”的限制模型就从线性问题变成带匹配的问题难度陡增。这种变体一般出现在更高难度的省选或 NOI 模拟中考察的是费用流建模或贪心反悔。如果你能把基础版的“rest 取 min”吃透再去看那种题会更容易理解。6.3 从“最少操作数”到“构造方案”有些题面会要求输出具体操作步骤。这种情况下除了计算最少的双位置操作次数外你还需要根据 f 数组反向构造方案。具体做法是从左到右扫描记录当前要求的覆盖额度每次在当前边界输出指定次数的“双位置加高”把剩余高度输出为“单点加高”。构造过程同样 O(n)但要注意输出顺序可能影响评测方式有些题允许任意顺序有些要求按字典序最小那就需要额外排序或调整。7. 个人复盘与实用建议我在做这套题的实际训练中发现最好的学习方法不是反复刷类似的题目而是做完之后停下来把题目翻译成自己的话复述一遍。这道题的翻译可以是“在一个只允许单点和相邻二元覆盖的模型下最少操作次数等价于总高度减去最多二元覆盖次数。”这个结论背下来毫无意义但如果你能自己推导出来就说明你真正掌握了它的结构。针对训练阶段的建议先用小规模数据把暴力验证程序写出来再对照贪心结果调试到一致然后再去想 O(n) 的优化。很多选手喜欢一上来就写最优解结果错了之后无法判断是对是错。暴力是最好用的调试工具尤其是这种带约束的构造题暴力生成的数据能覆盖各种边界情况。另外写代码时不要节省变量名。rest、take、ans 这种短而清晰的变量名比 a、b、c 在调试时好用得多。最后说一个小技巧这类题目如果用 Python 写务必用 sys.stdin.read 一次性读入所有数据避免多次调用 input 导致超时如果用 C关掉同步流ios::sync_with_stdio(false)也是常规操作但这一点对思路本身没有任何影响只影响通过率。实话说我在最初做这道题时也在“每步取最大”的错误贪心上栽过跟头。后来把问题转化成覆盖次数分配模型回头再看一切豁然开朗。这就是竞赛题最迷人的地方——同一个问题换一个视角复杂度从天壤之别变成一行递推。