最近给学员讲二分答案专题我总会把 P3853 [TJOI2007] 路标设置 放在第一节。原因很简单这题题干短、模型干净但它把“最小化最大值”这个套路展现得明明白白——你看完题觉得可以模拟动手写又发现处处是坑最后绕回二分答案一下子就把这类问题的解题框架立起来了。这道题要解决的问题是一条公路上已经有若干路标现在你最多能再增设 K 个路标希望所有相邻路标之间的最大距离尽量小输出这个最小的最大距离。无论你是备战信息学竞赛还是在打算法基础准备面试手撕代码拿这题把二分判定模型吃透都特别值。1. 读懂题意一个“看着可以模拟”的最值问题1.1 题面语言与输入输出先用大白话翻译一遍题面。公路总长度为 L坐标从 0 到 L。现在路上已经插着 N 个路标位置按升序给出。你手上还有 K 个路标可以新增。所谓“相邻路标之间的最大距离”就是指排序后任意两个相邻路标坐标差的绝对值取最大值。我们要做的是把这 K 个路标插到合适的位置让这个最大值尽量小然后输出它。输入格式很简单第一行三个整数 L、N、K第二行 N 个递增整数表示已有路标的位置。输出一个整数就是最优的“最小最大间距”。数据范围方面N 和 K 都能到 10^5 量级L 能到 10^7 量级所以复杂度必须控制在 O(N log L) 级别甚至更紧。这也是为什么这题能成为二分答案的入门经典——它逼着你放弃暴力。有一个细节值得注意很多版本的题面默认起点 0 和终点 L 处已经有路标所以直接对相邻输入的坐标求差值即可。如果你的输入版本里首尾没有路标一定要在数组里手动补上 0 和 L 再计算否则第一个区间和最后一个区间的约束就丢了。这一点后面讲坑的时候还会再说。1.2 “直接模拟”为什么会越想越乱拿到这道题很多人第一反应是我每次都找当前最大的相邻间距在它的正中间插一个路标插完 K 个再量一下不就完了吗这个思路非常自然但它有两个问题。第一个问题每插一个路标当前最大间距变小了第二大的间距会补上来。你每次都要重新找最大值如果写成扫描复杂度是 O(NK)如果写成优先队列代码量立刻膨胀。第二个问题更致命在最大区间正中间插一个真的是最优策略吗不一定。有些区间可能只需要插一个有些区间需要连续插两个甚至三个这种全局的“分配关系”靠单纯模拟很难处理干净。所以你会发现这条路能走但代码又长、维护又难正确性还要额外证明。我们需要的不是更聪明的模拟而是一个完全不同的视角把“构造最优解”换成“验证某个答案行不行”。1.3 先手算一个样例找感觉拿一个最小例子来感受一下。假设原有路标在坐标 0、5、10最多新增 2 个路标。如果只放 1 个最大间距能压到多少如果把新路标放在 5 附近0-5 和 5-10 两段里总有一段距离还是 5所以最大值至少是 5。这说明 1 个不够。放 2 个呢比如放在 2 和 8间距变成 2、3、3、2最大值是 3放在 3 和 7间距是 3、2、3、3最大值也是 3。能不能压到 2想让最大距离不超过 2每段长度 5 的区间至少要拆成 3 段也就是每个区间需要 2 个新增路标两个区间一共需要 4 个显然超预算。所以答案就是 3。这个手算过程其实已经包含了核心思想不是去构造“怎么插最好”而是直接问“如果要求最大间距不超过 x需要多少个新路标”。需要的数量小于等于 K就说明 x 可行否则 x 不可行。2. 单调性是核心把最优解问题转化成判定问题2.1 可行性关于答案大小是单调的刚才的小例子暴露了一个关键性质可行性是单调的。设“最大间距不超过 x”为条件那么 x 越大这个条件越宽松需要的路标就越少x 越小条件越苛刻需要的路标就越多。换句话说如果某个 x 可行那么所有比 x 更大的值一定也可行如果某个 x 不可行那么所有比 x 更小的值一定更不可行。这意味着可行的 x 在数轴上不是零零散散的点而是一段连续的右区间前面一段不可行从某个临界点开始全部可行。我们要找的答案就是这个临界点。对于这种“连续分界”的函书最经典的处理方式就是二分查找而不是逐个枚举。你可以想象成一个剪刀手在剪绳子绳子总长固定你要切成长度都不超过 x 的小段。x 越大要切的刀数越少x 越小刀数越多。给你 K 刀预算你自然想知道“最少能压到多长”——这本质上就是给 x 设一个预算约束然后二分找最小值。2.2 判定函数的设计思路有了单调性原问题就被拆成了两个子问题我们不再直接问“最优解是多少”而是猜一个候选答案 mid。写一个函数 check(mid)回答“如果要求最大间距不超过 mid最少需要新增多少个路标”然后看这个数量是否 ≤ K。只要 check 函数写得对二分就能在 log 级别的尝试次数里逼近答案。这里最妙的地方在于check(mid) 本身是个贪心问题逐个检查相邻原有路标的间距超了就在中间补路标补到“每个小区间都不超过 mid”为止。这个贪心是天然成立的因为每个区间是独立的区间内部怎么补只影响区间内部不会跨区间互相干扰。这也就是为什么我说这题特别适合入二分答案的门它的 check 函数不涉及复杂的动态规划也不需要特别的观察只要把“一个区间需要插几个”算清楚就行。2.3 上下界怎么定二分框架怎么搭二分的下界比较好想。如果坐标都是整数且严格递增相邻间距最小也是 1所以 l 可以从 1 开始。如果你在变式题里允许坐标重合那下界就老老实实从 0 开始。上界值得多说一句直接用 L 也能过但更严谨的取法是“原数组里的最大相邻间距”记为 r。原因很简单新增路标只会把区间越切越短答案不可能比“现有最大间距”更大。取 r 作为上界二分次数还能少几次更重要的是这个定义逼你想清楚了问题的边界。二分模板我习惯用左闭右闭的写法while (l r) { int mid (l r) 1; if (check(mid)) r mid; else l mid 1; } printf(%d\n, l);这里的 check(mid) 表示“mid 可行”可行就把右边界压到 mid不可行就把左边界推到 mid1。最终 l 和 r 会收敛到第一个可行的值也就是我们要的答案。3. check 函数的写法每个区间该塞几个路标3.1 一个区间的最少新增数ceil(d/x) - 1现在到整道题的核心。假设两个相邻原有路标的距离是 d候选的最大间距是 x。如果 d ≤ x这个区间本来就满足要求不需要新增如果 d x就一定要在里面插路标把整段拆成若干长度不超过 x 的小段。拆成几段至少是 ceil(d/x) 段因为每段长度上限是 x。要把 1 段拆成 t 段需要在中间放 t-1 个新路标。所以这一段贡献的新增路标数就是新增数 ceil(d / x) - 1这里注意“段”和“路标”的区别一段距离切成两段中间放 1 个路标切成三段中间放 2 个路标。很多人第一次写会在这里多算一个或少算一个所以这个公式建议直接刻在脑子里。3.2 为什么写成 (d-1)/xC 的整数除法默认向下取整所以 ceil(d/x) 可以写成 (dx-1)/x于是新增数可以写成 (dx-1)/x - 1。这个式子没错但它不够清爽。实践中我更推荐直接写成 (d-1)/x这两个式子在整数除法下是完全等价的。你可以自己验算几个例子d6、x3 时(d-1)/x 5/3 1正确因为 6 拆成两个 3中间只需要 1 个路标d7、x3 时(d-1)/x 6/3 2正确因为 7 拆成 331需要 2 个d3、x3 时(d-1)/x 2/3 0正确因为本身就没超。为什么它恰好等价直观解释是长度 d 的线段你在“距离 x 的整数倍”处切一刀最后一刀能不能省取决于 d 是不是 x 的整数倍。减掉那 1 个长度就是在提前去掉“恰好整除”造成的边界多算。这个细节是本题最大的坑也是写对 check 的关键后面的实战坑点里我还会单独展开。3.3 完整代码与剪枝#include bits/stdc.h using namespace std; const int MAXN 100005; int L, N, K; int a[MAXN]; bool check(int x) { int cnt 0; for (int i 1; i N; i) { int d a[i] - a[i - 1]; cnt (d - 1) / x; if (cnt K) return false; // 已经超预算提前退出 } return cnt K; } int main() { scanf(%d%d%d, L, N, K); for (int i 0; i N; i) scanf(%d, a[i]); int l 1, r 0; for (int i 1; i N; i) r max(r, a[i] - a[i - 1]); while (l r) { int mid (l r) 1; if (check(mid)) r mid; else l mid 1; } printf(%d\n, l); return 0; }代码很短但每一行都值得说清楚先算原数组最大间距作为上界 r然后二分的 mid 就是候选答案。check 里遍历所有相邻原有路标把每个区间需要的新增数加起来一旦超过 K 就立刻返回 false。提前返回这个剪枝很实用它在二分的前期能省掉大量无效计算尤其是当 x 很小、cnt 快速膨胀的时候。复杂度上check 是 O(N)二分次数约 log2(10^7) ≈ 24 次总操作量 2.4×10^6 量级即使是 Python 也能轻松跑完C 更是毫无压力。这也是为什么这类题二分答案比模拟优化靠谱得多。4. 实战场上最容易踩的四个坑4.1 整除方向d/x 和 (d-1)/x 的差别这个坑我见过太多人踩。直接把新增数写成 d/x在部分数据下看着没问题但一旦遇到整除边界就会出错。举两个例子你就明白了d6、x3 时d/x 2但正确答案是 1因为长度 6 正好分成两段 3中间只需要 1 个新路标d8、x4 时d/x 2正确答案是 1因为 8 分成两个 4中间同样只需要 1 个。问题出在哪d/x 是向下取整的段数而我们需要的是“从 1 段变成若干段时中间新加的隔断数”。段数等于 d/x 的向上取整隔断数等于段数减一。所以直接写 d/x 等于把“段数”和“所需新增数”混为一谈在 d 恰好是 x 倍数的时候会多算。我在推导时喜欢用一句话总结如果 d 是 x 的整数倍需要新增 d/x - 1 个如果不是整数倍需要新增 d/x 个。这两种情况合起来正好是 (d-1)/x 向下取整。所以代码里那一行直接背下 (d-1)/x 即可。4.2 二分模板的左右臂不一致二分答案的模板不止一种常见的有 lr 配合 rmid、lmid1也有 lr 配合 lmid1、rmid-1 然后记录答案的写法。两种都能 AC但最怕的就是混搭。有人写成 while(lr)里面却是 lmid1、rmid-1结果答案偏移或者死循环。还有一个方向陷阱我要特别提醒当你做的是“最小化最大值”时check 可行就往左压用 rmid当你做的是“最大化最小值”时比如后文要讲的跳石头、进击的奶牛check 可行反而要往右拉用 lmid而且 mid 要写成 (lr1)1 来防止死循环。这个方向问题比代码本身更容易翻车。4.3 上界取太大或太小都不行上界取 L 多数情况下没问题但取 L 之前先想清楚你的数组是否包含首尾边界如果包含最大间距肯定不超过 L用 L 只是效率略低如果不包含你补了 0 和 L 之后最大间距依然不超过 L。所以 L 作为上界往往是“能过的慢办法”。真正危险的反而是上界取太小。有人图省事把 r 初始化为某个“感觉够大”的数比如 N 或 K结果这个数比真实答案还小二分根本够不到答案区域最后输出一个明显偏小的数。如果实在不想分析r 就取原数组最大间距这是最安全的选择因为你已经有一个路标间距是这个值新增路标只会让它变小答案不会比它更大。4.4 坐标边界和排序问题原题样例里坐标严格递增且首尾一般都有路标所以直接 for 循环相邻差值就行。但如果你把这道题的代码拿去改造成其他题或者自己造数据验证排序问题立刻就会出现。乱序输入下不 sort算出来的“相邻差值”毫无意义。还有一种情况是首尾没有路标。比如你只有几个中间点问新增 K 个后整条线段上的最大空档。这时候必须先把 0 和 L 塞进数组再排序。否则第一个路标到起点的距离、最后一个路标到终点的距离都没有被约束check 的结果会比真实情况乐观很多。5. 这道题的思路还能用到哪两个现实布点案例5.1 从“路标”到任何离散设施的均匀布点刷题刷多了你会发现路标只是一个壳。壳下面藏的是一个特别通用的模型一条线段上已有一些“设施点”预算允许你再添加若干个问怎么让“最大空档”尽量小。这个模型在线下场景里随处可见。举一个我实际处理过的例子一条 200 米的仓库通道原来在 0 米、80 米、200 米处各有一个消防栓安全规范要求相邻消防栓的最大距离不能太大。预算只够再装 2 个消防栓问最多能压到多少。这几乎就是 P3853 的原样复刻只是把“路标”换成“消防栓”。用 check 来推演候选 mid60 时0-80 这段长度 80需要 (80-1)/60 1 个新增80-200 这段长度 120需要 (119)/60 1 个新增合计 2 个正好符合预算所以 60 可行。候选 mid59 时80 米段仍然只要 1 个但 120 米段需要 (119)/59 2 个合计 3 个超预算所以 59 不可行。答案是 60。这个判定过程完全不需要真的去一个个摆位置比人工画图规划快得多。5.2 从“新增”到“移除”和“覆盖”的迁移同样是这道题换个约束条件就变成另一种题型。如果预算不是“新增 K 个”而是“必须拆掉 M 个”问题就从最小化最大空档变成最大化最小间距——因为拆掉设施会拉大空档。模型还是这个模型但 check 函数和二分方向都要反过来写。再扩展一点如果是二维平面上的基站布点想让任意两个基站之间的覆盖空隙尽量均匀本质上还是在做“先把问题投影到一维再判断最大空隙”的检查。实际工程里没人真的一个点一个点去枚举放置方案而是把这个判定函数包在二分里反复调用。理解了这一点你会发现这道题的解题思想可以迁移到很多“先定约束、再验资源”的优化问题里。6. 同类题怎么打跳石头、进击的奶牛和数列分段6.1 变式一洛谷 P2678 跳石头跳石头是路标设置最经典的“反向变体”。一条河里有起点、终点和一些石头你可以移走 M 块石头问移走后选手从起点跳到终点的路径上最短跳跃距离的最大值能是多少。这题是“最大化最小值”和路标设置的“最小化最大值”正好相反。但二分骨架一点没变。check(x) 的逻辑是给定最短跳跃距离 x从起点出发遇到距离小于 x 的石头就跳过相当于移走遇到距离 ≥ x 的石头就踩上去统计一共跳过了多少块石头。如果跳过数量 ≤ M说明 x 可行。注意这里的单调性方向变了x 越大能踩的石头越少需要移走的石头越多可行性从真变假。所以二分要找的是“最后一个可行”模板变成while (l r) { int mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; }这个 (lr1)1 非常关键它保证在 l 和 r 只差 1 时不会死循环。很多同样会写路标设置的人第一次转到跳石头就在这里卡住。6.2 变式二洛谷 P1824 进击的奶牛进击的奶牛是另一道常见的“最大化最小值”模板题。C 头奶牛要住进 N 个牛棚牛棚位置固定你要让“最近的两头牛之间的距离”尽量大。check(x) 的逻辑变成从第一个牛棚开始只要当前牛棚和上一头牛所在牛棚的距离 ≥ x就放一头牛最后统计能放下 C 头牛。这个 check 和跳石头就像硬币的两面跳石头是“距离太近的石头就扔掉”进击的奶牛是“距离足够远的牛棚就入住”。一个在减石头一个在加奶牛但二分方向和模板完全一致。把这两题放在一起练你会发现“最大最小”和“最小最大”的判断本质上是同一套单调性思维。6.3 变式三洛谷 P1182 数列分段数列分段这道题稍微抽象一点给你一个正整数数列要分成连续的 M 段让每段数字和的最大值尽量小。这题是“最小化最大值”和路标设置方向一致。check(x) 改为从前往后扫描只要当前段累加和加上下一个数不超过 x就继续并进去一旦超过就新开一段统计最终段数是否 ≤ M。你会发现它的 check 结构还是在做同一件事给定上限 x贪心地消耗“连续资源”统计需要多少个分组/新增/移走。代码长得和路标设置的 check 几乎一个模子区别只是把“距离 d”换成了“累加和 s”。这道题验证了一个道理二分答案的难点从来不是二分本身而是能不能把“给定 x 怎么验证”写得准确。6.4 一套模板速查表把上面四道题放一张表里你就能看出统一性题目问法check 在算什么二分方向模板写法路标设置最小化最大间距新增路标数 ≤ K找第一个可行mid(lr)1; if(check) rmid; else lmid1跳石头最大化最小跳跃距离移走石头数 ≤ M找最后一个可行mid(lr1)1; if(check) lmid; else rmid-1进击的奶牛最大化最近距离能放奶牛数 ≥ C找最后一个可行mid(lr1)1; if(check) lmid; else rmid-1数列分段最小化最大段和分段数 ≤ M找第一个可行mid(lr)1; if(check) rmid; else lmid1我自己带学员的时候最常强调的一句话是一定要让别人一眼看出你的 check 函数在验证什么然后严格按照对应的二分方向写循环。只要这两件事不错剩下的就是边界和整数除法的基本功。我自己的体会是这题写到最后真正难的不是二分框架而是 check 函数里那一行整数除法。每次带新人我都会让他们先别急着看题解自己在纸上验算 d6、x3 和 d7、x3 两个例子能把 (d-1)/x 推导出来二分答案基本就通了。如果你也开始刷这类题建议从路标设置入手把模板打熟再去碰跳石头和奶牛梯度刚刚好。