[文章目录]
Description
一年一度的“跳石头”比赛又要开始了！
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有N块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走M块岩石（不能移走起点和终点的岩石）。
一开始以为是DP，后来一个学长嗯？了一下，说时间复杂度好像不是很妙的样子，我一看O（nm）！！！和暴力差不多了。所以经过指点，想起了零基础时的美好的二分答案2333
显然二分m，check()；也很好做，运用贪心思想，能不跳就不跳。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int ans,n,m,L;
int val[51000];
bool check(int x)
{
int now=0,re=0,cnt=1;
while(cnt<=n)
{
if(val[cnt]-now>=x) now=val[cnt],cnt++;
else re++,cnt++;
}
return re<=m;
}
int find()
{
int re=0,mid;
int l=0,r=L+1;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid))
re=mid, l=mid+1;
else r=mid;
}
return re;
}
int main()
{
scanf("%d%d%d",&L,&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
val[++n]=L;
ans=find();
printf("%d",ans);
return 0;
}时刻想着二分啊啊啊啊啊！！！