【题解】河中跳房子
【题目描述】
每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 < Di < L)。
在比赛过程中，奶牛轮流从起点出发，尝试到达终点，每一步只能从一个岩石跳到另一个岩石。当然，实力不济的奶牛是没有办法完成目标的。
农夫约翰为他的奶牛们感到自豪并且年年都观看了这项比赛。但随着时间的推移，看着其他农夫的胆小奶牛们在相距很近的岩石之间缓慢前行，他感到非常厌烦。他计划移走一些岩石，使得从起点到终点的过程中，最短的跳跃距离最长。他可以移走除起点和终点外的至多M (0 ≤ M ≤ N) 个岩石。
请帮助约翰确定移走这些岩石后，最长可能的最短跳跃距离是多少？
【输入描述】
第一行包含三个整数L, N, M，相邻两个整数之间用单个空格隔开。
接下来N行，每行一个整数，表示每个岩石与起点的距离。岩石按与起点距离从近到远给出，且不会有两个岩石出现在同一个位置。
【输出描述】
一个整数，最长可能的最短跳跃距离。
【样例输入】
25 5 2 2 11 14 17 21
【样例输出】
4
【题目分析】
这是一道 “二分+贪心”的典型例题
问题转化成下面这样：
我们有一条长度为L的河道，起点在位置0，终点在位置L。河道中有N个岩石，位置分别是给定的。奶牛需要从起点跳到终点，每次跳跃必须从一个岩石跳到另一个岩石。农夫约翰可以移除最多M个岩石（不包括起点和终点），目标是使得在所有可能的跳跃方案中，最短的跳跃距离尽可能大。
换句话说，我们需要找到一个最大的最短跳跃距离D，使得在移除不超过M个岩石后，剩下的岩石（包括起点和终点）之间的所有相邻跳跃距离都不小于D。
2. 为什么是二分？
因为我们需要找到最大的D，使得在移除不超过M个岩石后，所有相邻跳跃距离≥D。这是一个典型的“最大化最小值”问题，通常可以用二分查找来解决。 二分查找的思路 （1）确定搜索范围：D的最小可能值是0（如果移除所有岩石，直接从起点跳到终点），最大可能值是L（起点到终点的距离）。 （2）二分查找： 选择一个中间的D值（mid）。 检查是否可以移除不超过M个岩石，使得所有相邻跳跃距离≥mid。 如果可以，说明D可以更大，所以调整左边界。 如果不可以，说明D需要更小，所以调整右边界。 （3）终止条件：当左边界和右边界相遇时，找到最大的D。
3.如何验证D是否可行
编写一个函数isPossible(D)，判断是否可以移除不超过M个岩石，使得所有相邻跳跃距离≥D。具体步骤如下： （1）初始化： prev = 0（起点位置）。 count = 0（移除的岩石数量）。 （2）遍历所有岩石： 对于每个岩石，计算它与prev的距离。 如果距离 < D，说明需要移除该岩石（count++）。 否则，保留该岩石，更新prev为当前岩石。 （3）检查终点： 计算终点与最后一个保留的岩石的距离。 如果距离 < D，可能需要移除更多岩石（但终点不能移除，所以可能需要调整）。 返回count ≤ M。
4.例子
岩石位置：[2, 11, 14, 17, 21]，起点0，终点25，可以移除最多2个岩石。
二分查找过程：
初始：
left = 0，right = 25。mid = 12：起点0，第一个岩石2：距离2 < 12，移除2（count=1）。
下一个岩石11：距离11-0=11 < 12，移除11（count=2）。
下一个岩石14：距离14-0=14 ≥ 12，保留14（prev=14）。
下一个岩石17：距离17-14=3 < 12，移除17（count=3 > M=2）。
不可行。
验证
isPossible(12)：调整
right = 11。mid = 5：起点0，岩石2：距离2 < 5，移除2（count=1）。
岩石11：距离11-0=11 ≥ 5，保留11（prev=11）。
岩石14：距离14-11=3 < 5，移除14（count=2）。
岩石17：距离17-11=6 ≥ 5，保留17（prev=17）。
岩石21：距离21-17=4 < 5，移除21（count=3 > M=2）。
不可行。
验证
isPossible(5)：调整
right = 4。mid = 2：起点0，岩石2：距离2 ≥ 2，保留2（prev=2）。
岩石11：距离11-2=9 ≥ 2，保留11（prev=11）。
岩石14：距离14-11=3 ≥ 2，保留14（prev=14）。
岩石17：距离17-14=3 ≥ 2，保留17（prev=17）。
岩石21：距离21-17=4 ≥ 2，保留21（prev=21）。
终点25：距离25-21=4 ≥ 2。
count=0 ≤ M=2。
可行。
验证
isPossible(2)：调整
left = 3。mid = 3：起点0，岩石2：距离2 < 3，移除2（count=1）。
岩石11：距离11-0=11 ≥ 3，保留11（prev=11）。
岩石14：距离14-11=3 ≥ 3，保留14（prev=14）。
岩石17：距离17-14=3 ≥ 3，保留17（prev=17）。
岩石21：距离21-17=4 ≥ 3，保留21（prev=21）。
终点25：距离25-21=4 ≥ 3。
count=1 ≤ M=2。
可行。
验证
isPossible(3)：调整
left = 4。mid = 4：起点0，岩石2：距离2 < 4，移除2（count=1）。
岩石11：距离11-0=11 ≥ 4，保留11（prev=11）。
岩石14：距离14-11=3 < 4，移除14（count=2）。
岩石17：距离17-11=6 ≥ 4，保留17（prev=17）。
岩石21：距离21-17=4 ≥ 4，保留21（prev=21）。
终点25：距离25-21=4 ≥ 4。
count=2 ≤ M=2。
可行。
验证
isPossible(4)：调整
left = 5。mid = 5：之前验证过不可行。
调整
right = 4。终止：
left = 4，right = 4，输出4。
为什么输出是4？
因为在移除岩石2和14后，剩下的岩石是[11, 17, 21]，跳跃距离为：
0 → 11：11
11 → 17：6
17 → 21：4
21 → 25：4 最短跳跃距离是4，且移除的岩石数量是2 ≤ M=2。无法通过移除≤2个岩石得到更大的最短跳跃距离。
【参考答案】
#include<bits/stdc++.h> using namespace std; int rocks[100000];//假设岩石数量不超过 100000 // 判断是否可以通过移除最多 M 块岩石，使得最小跳跃距离至少为 D bool isPossible(int D, int N, int L, int M) { int prev = 0; // 起点 int count = 0; for (int i = 0; i < N; i++) { if (rocks[i] - prev < D) { count++; // 移除当前岩石 } else { prev = rocks[i]; // 保留当前岩石 } if (count > M) return false; } // 检查终点 if (L - prev < D) { count++; // 需要移除最后一个岩石（但终点不能移除） if (count > M) return false; } return count <= M; } int main() { int L, N, M; cin>>L>>N>>M; for (int i = 0; i < N; i++) { cin>>rocks[i]; } // 二分查找 int left = 0, right = L; int ans = 0; while (left <= right) { int mid = left + (right - left) / 2; if (isPossible(mid, N, L, M)) { ans = mid; left = mid + 1; } else { right = mid - 1; } } cout<<ans; return 0; }