企业官网建设流程全解析

1. 题目到底在说什么：先读懂跳石头的场景

1.1 一条河、一堆石头和一个“最大化最小值”的目标

P2678 跳石头这道题，是所有学二分答案的人几乎都绕不开的一道经典题。先花点时间把题干彻底拆开：起点是 0，终点是 L，起点和终点之间原本有 n 块岩石，每块岩石的位置严格递增，输入保证第 i 块石头的位置 dist[i] 是按从小到大给出的，所以不需要额外排序。你被允许移走最多 m 块岩石，起点和终点不能移走。运动员从起点出发，必须跳到相邻的“落脚点”，这个落脚点只能是你留下的岩石或终点。移走若干块石头之后，整条路径上所有相邻落脚点之间都会产生一个距离，这些距离里最小的那个，就是这场比赛的最短跳跃距离。题目要你移走石头，让这个“最短跳跃距离”尽可能大。

听起来有点绕，我换个直白说法：假设你的跳跃能力是 x，也就是说你每次都能跳过 x 米以上的距离，那么移走最多 m 块石头之后，从起点到终点能不能踩着剩下的石头顺利完成？题目要找的就是这个 x 的最大值。

原样例很典型：L=25，n=5，m=2，五块石头分别在 2、11、14、17、21。如果移走 2 和 14，剩下 11、17、21，相邻距离分别是 11（0 到 11）、6（11 到 17）、4（17 到 21）、4（21 到 25），最短的是 4。还能不能把最短距离提高到 5？你试着移走 2 和 21，剩下 11、14、17，距离是 11、3、3、8，最短只有 3，更差。所以在这个数据里，答案是 4。

1.2 为什么不能暴力枚举

看到“移走 m 块石头”这种字眼，新手第一反应往往是：从 n 块石头里选 n-m 块留下，然后算所有方案里最短跳跃距离的最大值。问题是组合数 C(n, n-m) 在 n=50000 时完全不可行，就算用二进制枚举也当场爆炸。哪怕用剪枝，最坏情况依然是指数级。另一个看似聪明的思路是枚举“移走哪些石头”，本质和枚举集合没有区别，同样不可行。

这类题有个共同特征：n 很大，答案是一个整数，而且答案的可行性随着数值变化呈现单调性。“n 大 + 答案单调”这两个信号一出现，十有八九要用二分答案，把“求最值”的问题转成“可行性判断”的问题。跳石头就是这样的典型。

1.3 把“求最值”换成“可行性判断”

假设现在手里有一个候选答案 d，问题就变成：能不能通过移走不超过 m 块石头，使得所有相邻跳跃距离都不小于 d？注意原题说“至多移走 m 块”，所以你可以少移，甚至一块都不移，只要能达到要求就行。

这个判定问题比原问题简单太多，用一趟贪心扫描就能完成。于是只需要对 d 进行二分，不断缩小范围，找到最大的可行 d。这就是二分答案的标准思路。

2. 二分答案的核心思想：从猜数字到最短跳跃距离

2.1 一个生活化的类比

你可以把二分答案想象成猜价格游戏。朋友心里想了一个 1 到 1000 之间的价格，你说 500，他说“高了”；你说 250，他说“低了”；你说 375，他说“低了”……每次根据反馈砍掉一半范围，很快就能逼近正确答案。

跳石头里的那个“价格”就是最短跳跃距离 d。只不过反馈方式不是“高了低了”，而是“check(mid) 是否可行”。我们取一个候选距离 mid，然后调用 check(mid) 去判断：如果 mid 可行，说明答案至少是 mid，答案在右侧；如果 mid 不可行，说明答案必须小于 mid，答案在左侧。每判断一次，搜索范围就缩小一半，原本要从 0 到 L 逐个验证，现在只需要 log2(L) 次，L 最大是 1e9，也只有大约 30 次。

2.2 单调性是二分的根基

二分答案能成立，根本原因是可行性关于 d 具有单调性：d 越小越容易满足，d 越大越难满足。严格一点说，如果 d 可行，那么对于任意比 d 小的 d'，d' 也一定可行，因为要求更宽松；反过来，如果 d 不可行，那么任何比 d 大的值更不可行。

所以整个 d 的取值范围可以看成两段：前面一段是可行区，后面一段是不可行区。我们要找的，就是可行区最右边的那个点。确认了单调性，二分就放心大胆地用。很多同学写二分答案翻车，不是二分模板的问题，而是没想清楚单调性——check 函数如果本身不具备单调性，后面的所有二分都是错的。

2.3 整数二分的边界：闭区间写法

写整数二分最怕边界出错。我个人常年用左闭右闭写法，也就是 l 和 r 都表示“可能答案”的范围，初始时 l=0，r=L。为什么 l 可以设成 0？因为答案最小可以趋近于 0，但实际上最短跳跃距离肯定是正整数，设成 0 只是让边界更安全，check(0) 一定返回 true。r 设成 L 也很好理解：最极端情况是把所有中间石头都移走，从起点直接跳到终点，距离就是 L，所以答案不可能超过 L。

之后的循环长这样：

int l = 0, r = L, ans = 0; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } }

每次 check 成功，就记录当前的 mid 作为备选答案，然后往右边找更大的；失败就往左边找。循环结束时 ans 就是要输出的答案。

2.4 关于二分会不会死循环

很多人被“整数二分死循环”吓到，其实只要避开一个坑就行：不要在 check 成功时写 l = mid，哪怕直觉上觉得“mid 可行，应该保留它”。左闭右闭写法搭配 l = mid + 1 和 r = mid - 1，是天然的防死循环组合。举一个临界例子，l=4，r=5，mid=(4+5)/2=4。如果 check(4) 为 true，ans=4，l=5，此时 l 和 r 相等，循环继续，mid=5；check(5) 如果是 true，ans=5，l=6 退出；如果 false，r=4 退出。无论哪种情况都不会原地打转。

3. 核心难点：check 函数到底怎么写

3.1 明确 check(x) 的含义

写一个函数 bool check(int x)，表示：在“最短跳跃距离至少为 x”的前提下，最少需要移走多少块石头，这个数量是否不超过 m。

注意这里求的是“最少移走数量”，不是随便移走 m 块就完事。因为检查可行性时，只要证明存在一种移法满足条件，而且移走的数量不超过 m 就行。如果能求出最少移走数 cnt，那么 cnt <= m 就是可行的充要条件。

3.2 贪心扫描的直观理解

从起点 0 开始，从左往右扫每一块中间石头。用变量 last 记录“上一块被保留的石头位置”，初始是 0。遇到当前石头位置 a[i]：

• 如果 a[i] - last < x，说明这块石头和上一块保留石头之间的距离小于 x。一旦保留它，路径上就会出现一个小于 x 的跳跃距离，直接违反条件，所以必须移走。
• 如果 a[i] - last >= x，说明距离足够，可以保留。此时把它设为新的 last，继续往后扫。

这个“能留就留”的贪心为什么正确？因为移走一块石头不会让后续任何间距变大，只会让你失去一个可用的落脚点；如果一块石头满足当前间距条件，你却在最优解里不保留它，那么把它加回来不会破坏任何已有的间距约束，反而可能让后面的选择更灵活。所以每一步能留就留，得到的移走数量一定是所有方案中最少的。

3.3 最后一段距离的处理：为什么可以简单 cnt++

扫描完所有中间石头后，last 是最后一块被保留的石头。此时还需要判断 last 到终点 L 的距离是否满足大于等于 x。这个判断很容易漏，很多人只在循环里处理中间石头，忘了终点，导致答案偏大。

如果最后 L - last < x，怎么办？终点不能移走，所以我们得让“倒数第一块保留石头”往后挪。但是所有中间石头都已经扫完了，唯一能做的就是：把最后一块保留石头也移走。注意，移走它之后，上一块保留石头（记为 pre）到终点 L 的距离一定大于等于 x。证明也简单：当初 last 能被保留，说明 last - pre >= x；现在移走 last，终点到 pre 的距离等于 (last - pre) + (L - last)，第一项 >= x，第二项 > 0，所以总和必然 > x。这意味着额外移走最后这一块石头就足够解决最后一段距离不够的问题，不需要连续移走多块。

所以代码只需要在循环后加一句：

if (L - last < x) cnt++;

这个 cnt++ 表面上是“多移走一块”，实际上移走的是刚才保留的 last。理解了这一点，很多题解的奇怪写法你就能看懂了。

3.4 复杂度和数据范围

check(x) 是 O(n) 的，二分次数是 O(log L)。L 最大是 1e9，大约 30 次，n 最大是 50000，所以总操作量约 150 万次。C++ 毫秒级跑完，Python 也完全能承受。这也是这道题敢把 n 开到 50000 的原因。

4. 完整代码实现与逐行注解

4.1 C++ 版本

#include <bits/stdc++.h> using namespace std; int L, n, m; int a[50005]; bool check(int x) { int cnt = 0; int last = 0; for (int i = 1; i <= n; i++) { if (a[i] - last < x) { cnt++; } else { last = a[i]; } } if (L - last < x) { cnt++; } return cnt <= m; } int main() { scanf("%d%d%d", &L, &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } int l = 0, r = L, ans = 0; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } printf("%d\n", ans); return 0; }

逐行解释一下关键点：a 数组开 50005，因为 n 最大 50000，多开几个防止越界。check 中 last 初始化为 0，代表起点。for 循环只遍历中间石头，最后单独处理终点。二分范围 [0, L] 已经论证过。ans 负责记录最后一个可行 mid，最终输出。

这里有个小优化：在 check 里如果 cnt 已经大于 m，可以直接 return false，因为 cnt 只会继续增加，不会减少。写在循环内部能节省一点时间，但要注意别把最后一段的判断跳过了——其实跳过也没关系，因为 cnt 已经超了，返回 false 是正确的。

4.2 Python 版本

def check(x): cnt = 0 last = 0 for pos in rocks: if pos - last < x: cnt += 1 else: last = pos if L - last < x: cnt += 1 return cnt <= m L, n, m = map(int, input().split()) rocks = list(map(int, input().split())) l, r, ans = 0, L, 0 while l <= r: mid = (l + r) // 2 if check(mid): ans = mid l = mid + 1 else: r = mid - 1 print(ans)

Python 版注意一点：rocks 列表必须是有序的，题目保证输入递增，所以没问题。如果 n=0，rocks 为空，check 里的 for 不执行，L - last = L，只要 L >= x，cnt=0，返回 true，二分最后输出 L，符合预期。这个边界经常被人忽略，但测试数据里很可能出现。

4.3 三个容易踩的坑

第一个坑是读入顺序。题目先给 L、n、m，再给 n 个石头位置，顺序千万别弄反。第二个坑是答案范围。有些人习惯把 r 设为 L+1 然后用左开右开模板，结果 mid 可能取到 L+1，check 里和 a[i] 比较时产生边界问题。闭区间更省心。第三个坑是 check 里的判断条件。必须写成a[i] - last < x时移走，>= x时保留。如果你写成<= x，会把刚好等于 x 的情况也判成不合法，答案会偏小一截。这个细节我当年就错过，样例还看不出来，直接全 WA。

5. 常见问题与排查技巧实录

5.1 样例过了，为什么提交全 WA

样例能过说明基本逻辑没大问题，全 WA 多半出在边界或者二分更新上。最常见的有三种：一是写成l = mid导致死循环或答案偏差；二是在 check 里把终点也当成普通石头处理，终点位置也被“移走”，语义错了，某些数据下会误判；三是忘了考虑 n=0 或 m 大于 n 的情况。建议提交前自己构造三组边界数据自测：n=0 且 m=0、m=n（全部移走）、还有 m 很小的情况。拿这些数据过一遍，心里就有底了。

5.2 二分死循环怎么排查

如果你发现程序一直跑不停，先把二分循环体打印出来，观察 l、r、mid 的变化。最常见的就是l = mid。举个例子，l=4，r=5，mid=4，check(4) 为 true，如果写成 l=mid，l 还是 4，r 还是 5，下一次又算 mid=4，死循环。有人会问：那 check(4) 为 true 不应该保留 4 吗？但二分答案要找的是“最大的可行值”，如果 4 可行，我们已经用 ans 记录了 4，接下来应该尝试 5，所以 l 要变成 5，而不是继续停留在 4。记住这个逻辑，就不会写错了。

5.3 为什么答案不一定是某个原始距离

细心的同学会发现，答案一定是某个相邻距离，比如样例里的 4 正好是原石头之间的一段距离。但二分答案并不需要依赖这个性质，它在整个整数域上搜索，靠单调性收敛到正确答案。就算你打印出 check 中那个可行的 mid，它恰好是某个距离，那也只是结果，不是方法的出发点。不要试图枚举所有距离，直接二分 0 到 L 即可。

5.4 提前退出带来的效率提升

如果 n 很大，check 可以在 cnt 超过 m 时立刻返回 false。比如下面这样：

bool check(int x) { int cnt = 0, last = 0; for (int i = 1; i <= n; i++) { if (a[i] - last < x) { cnt++; if (cnt > m) return false; } else { last = a[i]; } } if (L - last < x) { cnt++; } return cnt <= m; }

这样很多不可行的情况能在扫描中途终止，省下不少时间。注意，如果 cnt 在循环里已经超过 m，后面的终点判断无论如何都不可能让 cnt 变小，所以提前 return false 是安全的。

5.5 调试建议：把移走的石头打出来

我平时做这类题，check 写完后会在本地加一段调试代码，把每次移走的石头下标打印出来，然后对照样例手推一遍。比如样例中 check(5) 时，扫描顺序是：2 距离 0 小于 5，移走；11 距离 0 等于 5，保留；14 距离 11 小于 5，移走；17 距离 11 大于 5，保留；21 距离 17 小于 5，移走；最后 25 距离 21 小于 5，移走 last 也就是 21。这样你不仅能看到 cnt=4，还能理解为什么这个方案不可行。打印语句在提交前删掉就行。

6. 从跳石头看二分答案的通用套路

6.1 什么时候可以应用二分答案

一个很实用的判断信号：题目里出现“最大可能的最小值”或者“最小可能的最大值”，并且 n 的范围很大，直接枚举组合一定超时。比如“让所有牛之间距离的最小值最大”“把数组分成 k 段让每段和的最大值最小”都属于这一类。它们的共同点是：给定一个答案 x，能否满足条件这件事是容易判断的，而直接求最值却很困难。这时候二分答案就是最优解。

6.2 经典变式：最大化最小值 vs 最小化最大值

跳石头是“最大化最小值”，对应还有一个“最小化最大值”的经典题——比如把一根绳子切成若干段，求每段长度最大值的下限。看起来方向相反，但二分模板几乎一样，不同的只是 check 里的判断逻辑和统计方式。跳石头里的 check 是“间距不够就移走”，而“最小化最大值”的 check 往往是“当前段超过限制就开新段”。你只要把这两类题的 check 吃透，二分答案这一整类题型就通了。

6.3 一套可以反复套用的实战模板

这里给出一个偏抽象的模板，不绑定具体题目：

1. 确定答案可能所在的区间 [l, r]，并且想清楚区间的端点为什么合理。
2. 写出 check(x)，返回 x 是否可行。
3. 在主函数里 while(l <= r) 二分：mid=(l+r)/2，check(mid) 为真就更新 ans 并 l=mid+1，否则 r=mid-1。
4. 输出 ans。

这个模板我用过无数次，从没出过问题。唯一需要你动脑子的地方就是第 2 步——check 函数怎么写。二分只是把搜索范围缩小了，并不会帮你解决 check 本身的逻辑。跳石头之所以经典，就是因为它把“贪心 check”和“二分答案”结合得恰到好处，适合作为入门第一题。

做这类题时，我习惯先把单调性写在草稿纸上：x 越大，可行性越差，所以可行性序列是若干个 true 后面跟着若干个 false。然后直接闭区间二分。跳石头这道题我至少写了三遍，每写一遍都发现新的细节，最后是彻底想明白了终点段的 cnt++ 原理，才感觉自己真正会了二分答案。最后再分享一个小技巧：本地调试时把 check 里所有“移走”的石头下标打印出来，对照样例推演一遍，比盯着代码发呆有效得多。希望这篇拆解能让你少走一点我走过的弯路。