传送门 ↬\looparrowright

题目背景

一年一度的“跳石头”比赛又要开始了!

题目描述

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 nn 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 mm 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 len,n,mlen,n,m，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 len≥1len\geq 1 且 n≥m≥0n\geq m\geq 0。
接下来 nn 行，每行一个整数，第 ii 行的整数 di(0<di<len)d_i( 0 < d_i < len)， 表示第 ii 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式

一个整数，即最短跳跃距离的最大值。

输入输出样例

输入 #1

25 5 2
2
11
14
17
21

输出 #1

4

说明/提示

输入输出样例1说明：将与起点距离为 22 和 1414 的两个岩石移走后,最短的跳跃距离为 44 (从与起点距离 1717 的岩石跳到距离 2121 的岩石,或者从距离 2121 的岩石跳到终点)。
另：对于 $20\%$ 的数据，$0 ≤m ≤n ≤ 10$。对于 $50\%$ 的数据，$0 ≤ m≤ n ≤ 100$。对于 $100\%$ 的数据，$0 ≤m ≤n ≤ 50000$，$1 ≤ len ≤1000000000$。

分析

要求最小值的最大值，显然可以二分答案。
二分得到一个最短跳跃距离 xx，xx 合法的条件为：最短跳跃距离为 xx 时，至少需要搬走的岩石数量不超过 mm。
可以采用贪心策略检验 xx 的合法性。显然，每次跳跃的距离越大，略过的岩石就会越多；而略过的岩石是要搬掉的，这就意味着被搬走的岩石就会越多。为了让被搬走的岩石数量不超过 mm，就需要让每次跳跃的距离尽可能小；由于最短跳跃距离为 xx，那么就不妨假设每次都跳跃 xx 的距离。设置一个指针 ss，初始指向起点。若从 ss 向终点的方向，有距离 ss 为 xx 的岩石 tt，那么 ss 直接变为 tt；否则，就找到一个距离 ss 最近的位置 tt，tt 满足 t>st>s 且 dt−ds>xd_t-d_s>x，令 s=ts=t；这两种情况都可用库函数lower_bound解决，即找到第一个大于等于 ds+xd_s+x 的位置 tt。一般情况下，只需移除起始点和终止点中间的岩石，起始点为 ss，终止点为 tt，需要移除 t−s−1t-s-1 块岩石；需要注意的是，若最后一次跳跃的起始点距离终点的路程小于 xx，要将这个起始点的岩石也移除。
为了减少程序的分支，设置起点的编号为 00，终点编号为 n+1n+1，中间岩石的编号为 1∼n1\sim n；不妨设终点后方一个距离起点无穷远的点 n+2n+2，当最后一次跳跃的起始点距离终点的路程小于 xx，t=n+2t=n+2，仍然满足需要移除 t−s−1t-s-1 块岩石。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 50006
using namespace std;
int len,n,m;
int d[N];
inline bool check(int x)
{
	int i;
	if(x==0) return 1;
	//----------------------------------
	//s 当前节点
	//t 距离s路程不小于x的最近节点
	int s=0,t;
	int all=0;
	while(true)
	{
		t=lower_bound(d,d+n+2,d[s]+x)-d;
		all=all+t-s-1;
		s=t;
		if(s>=n+1) break;
	}
	//-----------------------------------
	return all<=m;
}
int main()
{
	cin>>len>>n>>m;
	int i;
	d[0]=0;
	d[n+1]=len;
	d[n+2]=0x7f7f7f7f;//n+2无穷大
	for(i=1;i<=n;i++) scanf("%d",d+i);
	int l=0,r=len;
	//误差范围为10
	while(r-l>=10)
	{
		int mid=l+r>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	int ans;
	while(l<=r)
	{
		if(check(l)) ans=l++;
		else break;
	}
	cout<<ans<<endl;
	return 0;
}