企业官网建设流程全解析

我第一次在评测平台上做到 P2678 跳石头这道题时，第一反应是：这不就是模拟吗？把石头一块一块搬走，每次选那个“影响最小”的石头不就行了？结果样例怎么都对不上，WA 到怀疑人生。后来才搞明白，这道题真正考的是“二分答案”——不是让你直接算出答案，而是在答案的取值范围内不断去猜、去验证，把“求最值”转化成无数次“可行性判断”。

如果你刚学完二分查找，想找个题目把二分答案彻底吃透，那这题再合适不过。它不涉及复杂数据结构，也不考数学技巧，核心就是三个东西：识别“最小值最大化”的题型、想明白答案的单调性、写对 check 函数。这篇文章我把这三件事拆开讲清楚，最后附上完整可提交的代码和我自己踩过三轮的 WA 复盘。

1. 从“直接模拟”的直觉误区，到二分答案的识别信号

1.1 先把题目翻译成人话

题目说白了是这样：有一条从起点 0 到终点 L 的河，河中间有 n 块石头，每块石头距离起点一个确定的位置。你现在最多能搬走 m 块石头（只能搬中间的，起点和终点不能动），搬完之后，人从起点出发，踩着剩下的石头跳到终点，要求整个过程中“每一次跳跃的距离”都不能太短。

问：把跳跃距离的最小值尽量做大，最大能大到多少？

我第一次读题时注意力全在“搬石头”这个动作上，以为这是个搜索题：枚举搬走哪些石头，然后计算最小跳跃距离，取最大值。n 最大能到 50000，这种枚举这辈子都枚举不完。

1.2 换个角度看问题：不直接求答案，而是猜答案

后来意识到一个关键转换：既然直接算“最短跳跃距离的最大值”很难，那不如反过来——我先猜一个距离 x，然后问自己一个问题：能否通过搬走不超过 m 块石头，使得任意相邻两块石头（包括起点和终点）之间的距离都不小于 x？

这个问题比原题好回答多了。你不需要考虑所有搬法，只需要沿着石头从左往右扫一遍，遇到距离不够的石头就搬掉，最后数一数搬了几块就行。

面试和竞赛里经常说“正难则反”，跳石头就是最经典的例子：最值不好直接求，就把它变成一个判定性问题。

1.3 这类题型的统一信号：“最小值最大化”

刷题多了你会发现，有一类题长得特别像：题目里同时出现“最大值”和“最小”两个词，或者要求“最大的最小”“最小的最大”。跳石头问的是“最短跳跃距离的最大值”，这就是典型的“最小值最大化”。

和它对称的是“最大值最小化”，比如把一段序列分成若干段，让每段和的最大值尽量小。这两种题型最统一的解法就是二分答案。以后只要看到这种“反着来的最值”，第一反应就应该是二分，而不是模拟。

2. 答案的单调性拆解：为什么“猜一个距离再验证”是可行的

二分答案之所以能在 O(log L) 次判断内解决问题，靠的不是运气，而是答案本身有严格的单调性。这个单调性是整道题的基石，值得花点时间讲透。

2.1 合法的答案集合是一个连续区间

假设当前猜的距离是 x。如果存在一种搬法，让所有相邻距离都不小于 x，就说 x 是“可行”的。

想一个很朴素的事实：如果 x 可行，那么任何比 x 小的数 y 肯定也可行。因为既然已经有一种搬法保证了“最小间距都不小于 x”，那这些间距当然也不小于 y，直接把同一套搬法拿来用就行。

反过来，如果 x 不可行，就是说搬再多的石头（但不能超过 m）都做不到“所有间距不小于 x”。那任何比 x 大的数 z 也更不可能了——一个方案如果能保证间距都不小于 z，那它显然也能保证不小于 x，这会产生矛盾。

所以“可行”和“不可行”在数轴上不会交错出现，而是一边倒的结构：从小到大，先是连续的一段可行值，然后到某个点之后全部不可行。我们要找的答案，就是分界线左边最后一个可行值。

2.2 用生活类比理解单调性

把二分答案想象成“考试划线”：

• 老师宣布及格线是 70 分，如果某个同学过了，那及格线改成 60 分他必然也过。
• 如果及格线是 70 分他没过，那把线抬到 80 分他更没戏。

所以及格线越定越高，从“全部人都过”一路到“全部人都挂”，中间只翻转一次。我们二分的任务就是找到那个“最后一个还能让所有人都过”的分数线。

2.3 二分的是数值，不是下标

这题很多人犯晕的点在于：以前学二分查找，是在一个数组里找 target，下标就是有序序列；现在跳石头里，我们二分的是“距离 x”，x 的取值从 0 到 L，本身也是从小到大排列的。

所以二分答案本质上还是二分查找，只是把“数组元素”换成了“所有可能的答案”，把“比较 a[mid] 和 target”换成了“调用 check(mid) 判断可行性”。

每次取中点的距离 mid，如果 check(mid) 返回 true，说明还有可能把答案再调大，就往右半边继续找；如果返回 false，说明这个距离太贪心了，得往左退。

3. check 函数怎么写：贪心搬石头与最容易漏的终点距离

二分答案的骨架大家都背得下来，真正决定生死的是 check 函数。它错了，整个二分就是在错误的基础上瞎猜。

3.1 贪心策略：间距不够，就搬掉当前这块石头

给定目标距离 x，我们需要统计最少要搬走多少块石头。这里的贪心策略非常直接：

• 维护两个变量：last表示上一块“被保留”的石头位置，removed表示已经搬走的石头数。
• 从左到右扫每一块石头。如果当前石头到last的距离小于 x，说明这两块之间的距离不达标，那就把当前这块石头搬走，last不动。
• 如果距离大于等于 x，说明这块石头可以留，更新last为当前石头位置。

为什么遇到距离不够就一定要搬“当前这块”，而不是搬“上一块”？因为上一块是好不容易保留下来的，它和更前面的石头已经满足距离要求了。如果把上一块搬掉，不仅当前问题没解决，还可能让更前面的间距也出问题，相当于一次动了两个位置。搬当前这块，只是让后面的石头自然往前靠，后续间距会更容易满足。

3.2 手工模拟一个例子

为了讲清楚，我们举一组小数据：L = 10，石头位置是 [2, 5, 7]，最多可以搬走 m = 1 块，假设当前猜的 x = 4。

• 起点 last = 0。
• 第一块石头在 2，2 - 0 = 2 < 4，搬走它，removed = 1，last 仍然是 0。
• 第二块石头在 5，5 - 0 = 5 >= 4，保留它，last = 5。
• 第三块石头在 7，7 - 5 = 2 < 4，搬走它，removed = 2，last 仍然是 5。
• 最后检查终点 L = 10，10 - 5 = 5 >= 4，通过。

removed = 2，超过 m = 1，所以 x = 4 不可行。手工验证也确实如此：只搬一块时，要么剩下 [5,7] 有 2 的距离，要么剩下 [2,7] 有 3 的距离，都撑不到 4。

3.3 最容易漏的坑：终点不是普通石头

很多人写 check 的时候只循环到 n，把终点检查忘了一干二净。但终点 L 也必须满足“和上一块保留石头距离不小于 x”这个约束。

怎么处理终点？有两种写法：

一种是在循环结束后单独判断：

if (L - last < x) { removed++; }

另一种是把终点也加入石头数组，作为第 n+1 个位置，然后循环到 n+1。我推荐第二种，理由很简单：循环逻辑统一，不容易漏掉边界。

不过这里有个非常微妙的细节：终点是不能被搬走的。如果终点和last的距离不够，代码里removed++其实不是在“搬终点”，而是在表达“这段距离靠当前保留方案无法收场，必须再多动一块更早的保留石头”。这是竞赛题解里约定俗成的计数技巧，你只要记住这个语义，就不会被它绕晕。

bool check(int x) { int last = 0; int removed = 0; for (int i = 1; i <= n + 1; i++) { if (pos[i] - last < x) { removed++; } else { last = pos[i]; } } return removed <= m; }

其中pos[n + 1] = L。

4. 完整代码与二分模板边界：选对 mid 取整方向才不会死循环

4.1 完整可提交版本

把 check 和其他部分拼起来，就是完整的可提交代码。这里我给一份 C++17 写法，注释写在关键位置。

#include <bits/stdc++.h> using namespace std; const int MAXN = 50005; int L, n, m; int pos[MAXN]; bool check(int x) { int last = 0; int removed = 0; for (int i = 1; i <= n + 1; i++) { if (pos[i] - last < x) { removed++; } else { last = pos[i]; } } return removed <= m; } int main() { scanf("%d%d%d", &L, &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", &pos[i]); } pos[n + 1] = L; // 输入如果保证递增可以不用 sort，排序求个心安 sort(pos + 1, pos + n + 1); int left = 0, right = L, ans = 0; while (left <= right) { int mid = (left + right) >> 1; if (check(mid)) { ans = mid; left = mid + 1; } else { right = mid - 1; } } printf("%d\n", ans); return 0; }

这段代码的时间复杂度是 O(n log L)。n 最大 50000，L 最大 1e9，二分大约执行 31 次，每次 check 扫一遍 50001 个点，总操作量在 150 万级别，跑起来非常快。

4.2 两种二分写法的对照

竞赛圈写二分答案主要有两套模板，一套是上面这种while (left <= right)配合ans记录，另一套是while (left < right)配合左端点收缩。我把它们对照列出来：

写法一（推荐新手用）：

int left = 0, right = L, ans = 0; while (left <= right) { int mid = (left + right) >> 1; if (check(mid)) { ans = mid; left = mid + 1; } else { right = mid - 1; } }

写法二（老手常用）：

int left = 0, right = L; while (left < right) { int mid = (left + right + 1) >> 1; if (check(mid)) { left = mid; } else { right = mid - 1; } }

两种写法最后得到的答案一致。区别在于：写法一不管当前这个 mid 是不是答案，都先记下来，再继续搜索；写法二把左边界一步步逼向答案。

4.3 mid 取整方向与死循环

死循环问题几乎全都出在写法二身上。如果你写成：

while (left < right) { int mid = (left + right) >> 1; // 下取整 if (check(mid)) { left = mid; // 此时可能原地踏步 } else { right = mid - 1; } }

当left和right只差 1 时，mid下取整等于left。如果check(left)为 true，执行left = mid后 left 根本没变，于是死循环。所以写法二里 mid 必须取(left + right + 1) / 2，也就是上取整，保证收缩时至少移动一位。

我自己写初学者题解时，通常建议用写法一。虽然多了一个ans变量，但逻辑直观，不用惦记取整方向，也不容易写出死循环。

4.4 二分上下界的确定

这题的下界设成 0，上界设成 L，理由很朴素：

• 最坏情况下，把所有中间石头都搬走，剩余路径就是起点直接跳到终点，距离为 L。所以任何情况下的最小跳跃距离都不可能超过 L，上界 L 够了。
• 任意情况下，最小距离至少是 0，下界从 0 开始不会有遗漏。有些人习惯从 1 开始，但万一答案就是 0，二分区间开头就把答案排除了，会出问题。

5. 实测踩坑复盘：三个 WA 版本的错误根源

这题我第一次交的时候，WA 得并不冤枉。下面把三轮真实踩坑过程复盘一遍，这些坑不看题解很难自己发现。

5.1 第一版错误：循环没包含终点

我最初写的 check 大概长这样：

bool check(int x) { int last = 0, removed = 0; for (int i = 1; i <= n; i++) { if (pos[i] - last < x) removed++; else last = pos[i]; } return removed <= m; }

看起来好像没问题，其实漏了最后一跳。举一个反例：L = 10，石头位置 [6]，m = 1，正确答案应该是 10（把唯一的石头搬掉，从 0 直接跳到 10）。但如果二分到 x = 4，我的 check 会这样走：

• pos[1] = 6，6 - 0 = 6 大于等于 4，retained，last = 6，removed = 0。
• 循环结束，removed = 0 小于等于 1，返回 true。

于是 x = 4 被误判为可行，答案就永远到不了 10。终点 10 和 last=6 之间的距离只有 4，刚好满足 x=4，但如果 x=5，终点距离 4 不达标，原代码仍然返回 true，就错了。所以循环必须把终点也算进去。

5.2 第二版错误：把终点当成“必须保留”导致误判

发现终点没处理后，我又改了一个看起来很合理的版本：

for (int i = 1; i <= n + 1; i++) { if (pos[i] - last < x) { if (i == n + 1) return false; // 终点不能搬，直接失败 } else { last = pos[i]; } }

结果更糟。还是那个例子：L = 10，石头位置 [6]，m = 1，x = 5。贪心过程：

• pos[1] = 6 保留，last = 6。
• 终点 10 - 6 = 4 < 5，直接 return false。

但明明可以把那块石头搬掉，从 0 直接跳到 10，完全可行。我的错误在于：终点距离不够时，贪心路径上的“上一块保留石头”是可以再牺牲掉的，不能一上来就宣告失败。这也是为什么标准写法里把终点距离不够也算作一次removed++，让二分结果在后续迭代中自然修正。

5.3 第三版错误：二分细节导致 TLE / 死循环

check 函数终于写对后，又遇到一次超时。原因是二分模板用了while (left < right)，mid 又选了(left + right) >> 1，并且 check 为真时left = mid。在二分到后期区间很小的阶段，mid 永远等于 left，check 又一直返回 true，程序就卡死在循环里。

这种问题最直接的排查办法：在循环里打印 left、right、mid 三个值。如果发现 mid 连续两次相同，基本就是取整方向写反了。修复方式很简单，要么改用写法一，要么把 mid 改成上取整。

复盘总结一下：跳石头的 WA，十有八九不是二分答案的思想错了，而是 check 函数的边界没抠干净，或二分模板的细节没吃透。

6. 从跳石头延伸出去的二分答案通用套路

6.1 怎么快速判断一道题能不能二分答案

我刷题积累下来的经验是：看到题目里有“最大值最小”或“最小值最大”这类描述，先别急着模拟，先想三个问题：

• 能不能枚举答案 x？
• 给定 x，能不能在可接受的时间内判断 x 是否可行？
• 可行/不可行是不是严格单调的？

三个答案都是“是”，那基本可以确定是二分答案。

跳石头是其中最容易套模板的一个，因为它判断可行性只需要一次线性扫描。实际中很多题的 check 可能要配合贪心、前缀和、区间合并甚至乱贪，但骨架完全一样。

6.2 通用 check 设计思路

设计 check 时，不要想着把“最优方案”完整算出来，只想着“当前这个 x 到底能不能满足约束”。这是一个巨大的思维转变：

• 原问题：求最优解。
• check 问题：给定 x，判断存不存在一种方案，让所有指标都不超过/不少于 x。

为了判断存在性，通常用贪心：从第一个位置开始，能留就留，不能留就补。跳石头里的贪心是“间距不够就搬掉后面的”；其他场景里可能是“区间不够就新开一段”“资源不够就加一个容器”等等。核心都是局部决策，不需要全局枚举。

6.3 练习路线与我的个人习惯

如果想把二分答案彻底吃透，我建议按这个顺序练习：

• 先写跳石头，把while (left <= right)这套模板练熟。
• 再找一个“最大值最小化”的题做对比，比如序列分段、让最大值尽可能小。
• 最后尝试一个 check 里需要贪心+排序的题，把两种套路合起来。

我现在拿到这类题，第一步永远不会去看怎么直接求答案，而是先写一个check(x) 是否可行的函数，再套二分模板。这个顺序一旦固定下来，正确率和速度都会明显提升。跳石头作为二分答案的“开山怪”，值得你反复写三遍：第一遍理解思路，第二遍默写代码，第三遍闭眼讲清单调性。三遍之后，这类题就是送分题了。