【题目来源】
洛谷：[P2678 NOIP 2015 提高组] 跳石头 - 洛谷 (luogu.com.cn)
【题目描述】
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 \(N\) 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 块岩石（不能移走起点和终点的岩石）。
【输入】
第一行包含三个整数 \(L,N,M\)，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 \(L\ge 1\) 且 \(N\ge M\ge 0\)。
接下来 \(N\) 行，每行一个整数，第 \(i\) 行的整数 \(D_i(0\lt D_i\lt L)\)， 表示第 \(i\) 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
【输出】
一个整数，即最短跳跃距离的最大值。
【输入样例】
25 5 2
2
11
14
17
21
【输出样例】
4
【解题思路】
【算法标签】
《洛谷 P2678 跳石头》 #贪心# #二分# #NOIP提高组# #2015#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量定义
int length, n, m, a[50005], last; // length: 道路总长度, n: 已有石头数, m: 可移除石头数// a[]: 存储相邻石头间距, last: 记录上一个石头位置int main()
{// 输入道路总长度、已有石头数和可移除石头数cin >> length >> n >> m;// 初始化上一个石头位置为0（起点）last = 0;// 输入每个石头的位置并计算相邻石头间距for (int i = 0; i < n; i++) {int now; // 当前石头位置cin >> now;a[i] = now - last; // 计算当前石头与前一个石头的间距last = now; // 更新上一个石头位置}// 计算最后一个石头到终点的间距a[n] = length - last;// 特殊情况处理：如果可移除石头数等于已有石头数if (n == m) {cout << length << endl; // 直接输出道路总长度return 0;}// 二分查找初始化int l = 1, r = length / (n - m); // l: 最小可能间距, r: 最大可能间距// 二分查找过程while (l <= r) {int tmp, k = 0; // tmp: 临时累计间距, k: 需要移除的石头数int mid = l + (r - l) / 2; // 中间值（当前猜测的最小间距）// 检查当前mid是否可行for (int i = 0; i <= n; i++) {tmp = a[i]; // 初始化为当前间距// 如果当前间距小于mid，则合并下一段间距while (tmp < mid && i <= n) {i++;tmp += a[i]; // 合并间距k++; // 增加需要移除的石头数}}// 根据检查结果调整二分范围if (k <= m) l = mid + 1; // 移除石头数不足，可以尝试更大的间距else r = mid - 1; // 移除石头数过多，需要减小间距}// 输出最终结果（最大可能的最小间距）cout << r << endl;return 0;
}
【运行结果】
25 5 2
2
11
14
17
21
4