1. 从“河中跳房子”到二分答案：一个经典思维的诞生
如果你刚开始接触算法竞赛或者刷题，看到“1247：河中跳房子”这个标题，可能会觉得有点摸不着头脑。这听起来像是个游戏或者物理题，怎么就成了经典的算法例题？我第一次遇到它时也有同样的疑惑，但真正动手做下来才发现，这道题简直是理解“二分答案”这个核心思想的绝佳敲门砖。它没有复杂的图论结构，也没有繁琐的动态规划状态转移，就是用一个最朴素的场景，逼着你去思考一个根本问题：当答案本身难以直接求解，但给定一个“候选答案”后，我们能快速判断它是否可行时，我们该怎么办？
“河中跳房子”描述的场景非常直观：有一条河，河中间有N个石头（房子），它们与起点的距离是已知的。现在我们要从起点跳到终点，每次跳跃必须落在石头上，并且跳跃距离不能小于一个给定的值。问题是，在必须移走恰好M块石头的情况下，如何安排移走哪些石头，使得最终能够完成跳跃的最短跳跃距离尽可能大？这个“尽可能大的最短跳跃距离”，就是我们要求解的答案。
为什么这个问题适合用二分答案？因为答案——那个最短跳跃距离——是一个整数，并且存在一个明确的边界。想象一下，如果允许的跳跃距离非常小，比如1，那么你几乎可以踩着所有石头过去，移走M块石头后肯定也能过去，所以这个答案是“可行”的。如果允许的跳跃距离非常大，大到超过相邻石头间的最大间隔，那么你移走M块石头后，必然存在一段你跳不过去的空隙，所以这个答案是“不可行”的。于是，在“可行”与“不可行”之间，存在一个临界点。我们的目标就是找到这个最大的、依然可行的跳跃距离。手动去猜这个数显然效率低下，而二分查找，正是用来在有序范围内快速定位这种临界点的利器。
网络上相关的热词如“二分答案”、“二分查找”、“贪心算法”都指向了这里。很多人学二分，只记住了在有序数组里找某个数，却不知道“二分答案”才是二分思想更具威力的应用。这道题就是一个完美的桥梁，它要求你跳出“在给定序列中查找”的定式思维，转而去在一个答案的可能区间里，利用一个判断函数来缩小区间。这个思维模式的转换，是解决一大批最优化问题的关键，从安排会议时间到分配资源，其内核都是相通的。
2. 问题拆解：定义、约束与核心挑战
在动手写代码之前，我们必须把题目嚼碎了咽下去，理解每一个条件背后的意图。这不仅仅是读懂题目，更是为了设计出正确的“可行性判断”函数，这是二分答案的灵魂。
2.1 问题要素的精确翻译
首先，我们把生活化的描述翻译成程序员熟悉的语言：
- 输入：河的长度L（起点到终点的距离），石头数量N（不包括起点和终点），必须移走的石头数M，以及N块石头距离起点的位置（升序给出）。
- 隐含点：起点（位置0）和终点（位置L）是固定的，不能移动。我们跳跃的“舞台”就是由起点、终点以及剩下的 (N - M) 块石头构成的。
- 动作：从起点开始，每次跳到下一块剩余的石头，最终跳到终点。每次跳跃的距离，就是两块石头位置之差。
- 目标：在移走恰好M块石头后，找出一种保留石头的方案，使得所有跳跃距离中的最小值最大。输出这个最大的最小值。
这里有一个非常关键的理解点：我们不是要找出移走哪M块石头，而是要找到一个最大的距离D，使得存在一种移走M块石头的方法，让剩下的石头（包括起点终点）中，任意相邻两块的距离都至少为D。前者是一个具体的组合方案，后者是一个数值目标。二分答案帮我们找到的是后者。只要我们能判断某个D是否可行，我们就能用二分逼近最大的那个D。
2.2 为什么贪心算法是可行性判断的“最优解”？
给定一个候选的“最短跳跃距离”D，如何判断在移走不超过M块石头的前提下，能否实现所有跳跃距离都 >= D？
一个最直接的思路是模拟跳跃过程。我们从起点（位置0）开始，看向下一块石头。如果当前石头与下一块石头的距离 >= D，那么我们可以安全地跳过去，并把下一块石头作为新的起点。如果距离 < D，说明这块石头太近了，如果我们不跳过去，就无法到达终点（因为我们必须按顺序跳）。那么唯一的办法就是移走这块距离太近的石头，然后继续比较当前石头与再下一块石头的距离。
这个过程天然就是一个贪心算法：我们在每一步都做出局部最优选择——只要石头够远就跳过去，不够远就移走它。为什么贪心在这里是正确的？因为我们的目标是让所有间隔 >= D，并且希望移走的石头尽可能少。如果当前石头和下一块石头距离小于D，保留下一块石头必然导致这段间隔不达标。移走它，是为后续的间隔创造可能（让当前石头直接对接更后面的石头）。这个决策只影响当前这一段，不会对未来的决策产生后效性，因此贪心是有效的。
具体判断函数check(D)的逻辑如下：
- 初始化
last_pos = 0（起点位置），removed = 0（移走石头计数）。 - 遍历每一块石头（位置为
stone[i]）：- 计算
stone[i] - last_pos。 - 如果距离 < D，说明石头
i太近，必须移走：removed++。 - 如果距离 >= D，说明可以跳到石头
i，更新last_pos = stone[i]。
- 计算
- 遍历结束后，不要忘记终点！计算
L - last_pos（最后一块保留的石头到终点的距离）。如果这个距离也 < D，那么意味着即使调整石头，从最后一块石头也无法跳到终点，这个D肯定不可行。实际上，在贪心过程中，如果最后一段距离小于D，我们已无石头可移（终点不能移），所以直接判定不可行。 - 判断
removed <= M。如果成立，说明用不超过M次的移除操作，可以实现所有跳跃 >= D，D是可行的；否则不可行。
注意：这里有一个非常重要的细节，也是容易出错的地方。
check(D)函数判断的是“能否在移走不超过M块石头的情况下实现条件”。题目要求是“移走恰好M块”，那会不会有“移走少于M块就能满足条件，导致我们找到的不是题目要求的解”的情况？实际上，如果某个D满足“移走 <= M 块石头即可”，那么它一定是可行的。因为我们可以通过额外移走一些无关紧要的石头（比如在已经很远的间隔中间再移走一块），凑足恰好M块，而这并不会降低已有的最短跳跃距离。所以，check(D)的条件是宽松的，这保证了二分过程的正确性。我们最终找到的，是满足“移走 <= M 块石头即可”的最大D，它必然也对应着一种“移走恰好M块石头”的方案（可以通过额外移除来凑数）。
3. 二分查找的边界与循环设计：避开死循环的坑
理解了check(D)，我们就有了在答案空间里导航的指南针。接下来，我们需要确定搜索的起点和终点，并设计一个永不迷路的二分循环。
3.1 答案边界的确定
答案（最短跳跃距离的最大值）最小是多少？理论上可以是0，但0没有实际意义，且我们的判断函数在D=0时总是成立。更实际的下界是1。答案最大是多少？一种朴素的认为是河的长度L，但显然不可能跳那么远。一个更紧的上界是L本身（如果你能一脚从起点跳到终点）。但在二分时，我们通常设置一个安全的、肯定不可行的上界。因为当D大于任意两块石头（包括起点终点）之间的间隔时，必然不可行。所以我们可以设置left = 1,right = L。为了确保完全覆盖，有时会设置right = L + 1，这样即使check(L)为真，我们的二分区间也能容纳它。
在我的实践中，更推荐一种清晰且不易出错的方式：
int left = 1; // 最短跳跃距离至少为1 int right = L; // 最长不会超过河的长度 // 或者，考虑到如果所有石头都移走，最短距离就是L，所以right=L是合理的。3.2 二分循环的“左闭右开”与“左开右闭”抉择
这是二分查找最容易写出死循环的地方。关键在于明确你维护的区间含义。
- 我们寻找的是最后一个满足
check(mid) == true的D。 - 假设我们维护的区间是
[left, right]，其中check(left)为真，check(right)为假。我们的目标是不断缩小这个区间，直到left和right相邻。
我强烈推荐并使用“左闭右开”的写法，即区间表示为[left, right)。它的循环不变式是：left指向一个可行的答案，right指向一个不可行（或未探索）的边界。最终，当left + 1 == right时，left就是我们要找的最大可行解。
对应的循环模板如下：
while (left + 1 < right) { int mid = left + (right - left) / 2; // 防止溢出 if (check(mid)) { left = mid; // mid可行，说明答案至少是mid，将左边界推进到mid } else { right = mid; // mid不可行，说明答案必须小于mid，将右边界收缩到mid } } cout << left << endl; // 循环结束时，left就是最大可行值这种写法的好处非常明显：
- 永不退循环：条件
left + 1 < right保证了区间内至少有两个元素时才需要循环。当区间缩小到[left, left+1)时，循环结束。 - 更新清晰：因为区间是右开的，当
mid可行时，我们将left设为mid，这很自然。当mid不可行时，我们将right设为mid，因为mid本身已经不可行，新的右边界应该是它（开区间不包含mid）。 - 答案明确：循环结束后，
left就是最后一个被验证可行的值，直接输出即可。
对比常见的while (left <= right)写法，那种写法需要处理mid的加减1，并且最终答案的存储变量（是left还是right还是ans）容易混淆。“左闭右开”模板将答案的维护隐含在了区间边界里，逻辑更简洁，几乎可以成为二分答案问题的标准写法。
3.3 一个完整的算法流程梳理
- 读入L, N, M以及石头位置数组
stones。为了方便处理，可以在数组开头插入0（起点），末尾插入L（终点）。 - 定义
check(int d)函数，实现上述贪心逻辑，返回布尔值。 - 初始化二分边界
left = 1,right = L + 1（或right = L，但需确保check(L)为真时也能正确处理）。 - 执行“左闭右开”的二分循环。
- 输出
left。
4. 代码实现、测试与极端情况分析
理论清晰之后，我们来落地成代码，并思考一些边界情况，确保我们的解决方案是健壮的。
4.1 完整的C++代码实现
#include <iostream> #include <vector> #include <algorithm> using namespace std; int L, N, M; vector<int> stones; // 判断是否能在移走不超过M块石头的情况下，使得最短跳跃距离至少为d bool check(int d) { int last_pos = 0; // 起点位置 int removed = 0; // 遍历所有石头 for (int i = 0; i < N; ++i) { if (stones[i] - last_pos < d) { // 距离太近，必须移走当前石头 removed++; if (removed > M) { // 移走数量已超限，提前返回false return false; } } else { // 可以跳过去，更新上一个位置 last_pos = stones[i]; } } // 检查最后一块保留的石头到终点的距离 // 注意：终点L已经包含在stones数组末尾了吗？这里假设没有。 // 更稳妥的做法是，将终点L也视为一块“石头”加入数组，这样循环内就包含了终点判断。 // 以下是未将终点加入数组时的判断： if (L - last_pos < d) { return false; // 最后一段跳不到终点 } return removed <= M; } int main() { cin >> L >> N >> M; stones.resize(N); for (int i = 0; i < N; ++i) { cin >> stones[i]; } // 为了方便，可以对石头位置排序（题目虽说是升序给出，但排序是个好习惯） sort(stones.begin(), stones.end()); // 二分查找 int left = 1; int right = L + 1; // 右开区间，L+1是一个肯定不可行的值（因为最大距离是L） while (left + 1 < right) { int mid = left + (right - left) / 2; if (check(mid)) { left = mid; // mid可行，尝试更大的 } else { right = mid; // mid不可行，缩小范围 } } cout << left << endl; return 0; }代码优化点：如注释所述，将终点L作为一块“石头”插入stones数组末尾，可以使check函数逻辑更统一，无需单独判断最后一段。修改如下：
stones.push_back(L); // 在输入并排序后，加入终点 N = stones.size(); // 更新石头数量（包含了终点） // 修改check函数，移除对 L - last_pos 的单独判断，因为终点已在数组中。 bool check(int d) { int last_pos = 0; int removed = 0; for (int pos : stones) { // 现在stones包含了终点 if (pos - last_pos < d) { removed++; if (removed > M) return false; } else { last_pos = pos; } } return true; // 如果能遍历完所有“石头”（包括终点），说明成功到达 }4.2 极端情况与测试用例
任何健壮的算法都需要考虑边界。
- 情况一：M = 0（一块石头都不能移）。此时问题退化为：给定间隔，求最小间隔的最大值？实际上，答案就是所有相邻石头（包括起点终点）间隔的最小值。我们的算法能工作吗？可以。
check(D)函数会尝试移走距离小于D的石头，但因为M=0，一旦需要移走就会返回false。二分会找到最大的那个D，使得没有任何间隔小于D，即所有间隔都 >= D。这个D就是最小间隔。 - 情况二：M = N（所有石头都可以移走）。此时我们可以移走所有石头，直接从起点跳到终点。那么最大的最短跳跃距离就是河的长度L。我们的算法中，
check(L)会成功吗？在贪心过程中，因为起点0到任何一块石头的距离都小于L（除非石头就在L），所以所有石头都会被标记为移走，removed = N，满足removed <= M。并且最后last_pos还是0，终点L到0的距离等于L，满足条件。所以check(L)返回true。二分会找到L。 - 情况三：石头位置有重复。题目通常保证位置互异，但如果输入有重复，我们的算法依然有效。对于两个位置相同的石头，它们之间的距离为0，在任何D>0的情况下，第一块都会被保留，第二块会被移走（因为距离0 < D）。
- 情况四：L很小，N很大。二分查找的复杂度是 O(logL * N)，在常规数据范围内（L<=10^9, N<=50000）完全可行。
4.3 与“最小值最大化”同类问题的对比
“河中跳房子”是“最小值最大化”问题的典型代表。类似的还有：
- “进击的奶牛”：在一条数轴上放N个牛棚，要放入C头牛，使得任意两头牛之间的最小距离最大。解法几乎一模一样，
check(d)函数判断能否在保证牛之间距离至少为d的情况下放下所有牛。 - “砍树”：有N棵树，需要砍下M米长的木材，锯子的高度为H，树木高于H的部分会被砍下。求最大的H，使得砍下的木材总长度至少为M。这里
check(H)计算木材总长度是否 >= M。 - “分配预算”：将总额为M的预算分配给N个项目，每个项目有一个最低需求和最高需求，求在满足所有项目最低需求后，能使获得预算最少的那个项目得到的预算最大值。
check(x)判断能否在满足每个项目至少获得x预算的前提下，分配完总预算。
它们的共同模式是：答案是一个数值，其可行性与数值大小呈单调关系（通常，数值越大越难满足条件），并且存在一个判断给定数值是否可行的函数。识别出这种模式，就立刻可以套用二分答案的框架。
5. 从二分答案到更广阔的算法思维
通过“河中跳房子”这个具体的例子，我们深入演练了二分答案的完整流程。但这道题的价值不止于此，它更像一个引子，让我们看到算法思维是如何层层递进的。
5.1 贪心与二分的结合：1+1>2
这道题的精妙之处在于它将贪心和二分完美结合。贪心算法负责在给定约束下的快速可行性判断（check函数），其时间复杂度是O(N)。二分查找则负责在巨大的答案空间（1到L）中进行高效搜索，时间复杂度是O(logL)。两者结合，总复杂度为O(N logL)，轻松处理大规模数据。这种“二分外壳 + 贪心/其他算法内核”的结构，是解决许多最优化问题的标准套路。关键在于，你必须能够写出一个正确的、单调的check函数。
5.2 调试二分：当答案不对时怎么办？
二分查找的bug往往难以察觉。如果你得到的答案不对，可以按以下步骤排查：
- 验证
check函数：这是最容易出错的地方。构造几个小例子，手动模拟check(D)的过程，特别是边界情况（D很小、D很大、M=0、M=N）。确保你的贪心逻辑是正确的。 - 验证二分边界：打印出循环过程中
left,right,mid和check(mid)的值。观察区间是否在正确收敛。确保你的初始right设置得足够大（是一个肯定不可行的值）。 - 验证循环条件：确认你的循环最终会停止。对于“左闭右开”模板，
while (left + 1 < right)是安全的。 - 验证最终答案：循环结束后，输出的是
left还是right？根据你的区间定义来确认。在我们的模板里，输出left。
5.3 举一反三：识别二分答案的适用场景
在以后的刷题或工作中，如何判断一个问题是否能用二分答案解决？问自己三个问题：
- 问题的答案是一个数值吗？（通常是最大或最小的某个指标）。
- 如果我猜一个答案，我能相对容易地判断它是否“可行”吗？（即能写出
check函数）。 - 可行性和数值大小之间是否存在单调性？（例如，对于“最小值最大化”问题，数值越大越难满足；对于“最大值最小化”问题，数值越小越难满足）。
如果这三个问题的答案都是“是”，那么二分答案就很可能是一个高效的解决方案。它把求解最优值的问题，转化为了若干个判定性问题，极大地简化了思维难度。
回过头看“1247：河中跳房子”，它之所以经典，就是因为它干净利落地呈现了这个思维范式。没有多余的干扰，直指核心。吃透这道题，你收获的不仅仅是一个AC的代码，更是一种面对复杂最优化问题时，化繁为简、分而治之的强大武器。下次再遇到“最大的最小”、“最小的最大”这类字眼，你会条件反射般地想到：也许，可以试试二分答案。
