✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：杂题讲解
📝原题地址：跳石头
📣专栏定位：在这里我将整理一些其他比赛或面试的题解~
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪
问题描述
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。
组委会已经选择好了两块岩石作为比赛起点和终点。
在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。
在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。
由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。
输入格式
输入文件第一行包含三个整数 L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。
接下来 N 行，每行一个整数，第 i 行的整数 Di（0 < Di < L） 表示第 i 块岩石与起点的距离。
这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
输出文件只包含一个整数，即最短跳跃距离的最大值。
数据范围
0≤M≤N≤500000
1≤L≤109输入样例：
25 5 2 2 11 14 17 21输出样例：
4
思路
这道题是二分套路题中的经典问题 —— 最小值最大化，除此之外还有最大值最小化问题，解法和这个差不太多。
我们先来考虑暴力法如何做，需要枚举 n 块石头中选取 m 个石头的所有组合，时间复杂度直接爆炸！
所以需要优雅一点的暴力，同样是枚举，不过我们枚举的是最短距离的最大值 d。对这个临界值进行二分，每次二分都去判断当前最短距离的最大值是否能通过移走 m 个以内的石头达到中位值 mid，如果满足条件，则使 left=mid，反之使 right=mid-1，因为我们要使最小值尽可能的大，所以当 mid 已经满足条件时我们任然要继续往更大的值进行尝试，另外 mid 如果此时已经满足条件则有可能就是最终答案，所以需要用 left 保存下来。
另外，我们 check 中可以采用贪心思想：
- 如果当前石头和上一块石头的距离小于
len，则将当前石头拿走。这是因为如果某个最优解中是拿走了上一块石头，那么我们可以改成留下上一块石头，拿走当前这块石头，这样总共拿走的石头数量不变，所以当前选法也是一组最优解。 - 如果当前石头和上一块石头的距离大于等于
len，则将上一块石头更新成当前这块。
扫描结束后观察拿走的石头数量是否小于等于 m，如果小于等于则满足条件。
代码
#include<cstdio>
int len, n, m;
int stone[50005];
bool check(int d) { //检查距离d是否合适int num = 0; //num记录搬走石头的数量int pos = 0; //当前站立的石头for (int i = 1; i <= n; ++i)if (stone[i] - pos < d) num++; //第i块石头可以搬走else pos = stone[i]; //第i块石头不能搬走if (num <= m) return true; //要移动的石头比m少，满足条件else return false; //要移动的石头比m多，不满足条件
}
int main() {scanf("%d%d%d", &len, &n, &m);for (int i = 1; i <= n; ++i) scanf("%d", &stone[i]);stone[++n] = len;int L = 0, R = len, mid;while (L < R) {mid = L + (R - L + 1) / 2;if (check(mid)) L = mid; //满足条件else R = mid - 1; //不满足条件，说明mid大了，调小一点}printf("%d\n", L);return 0;
}
