首先将石头位置排个序,以便处理方便。
从位置的小到大扫遍所有石头,用一个变量存储上一个跳到的点。第一个与这上一个点的距离大于等于x的石头即是下一个跳到的点。因为我们要取最优状态,所以要保证跳过的石头数最少。
这样,便求出了这个x是否可行,如果可行,那就往右边二分,但要记得范围要包括x;若不行,则往左边二分,右限制不包括x。然后,二分到左右边界相等,输出即可。
#include<bits/stdc++.h>
using namespace std;
int sto[100000];
int main()
{
int s,n,m;
scanf("%d%d%d",&s,&n,&m);
int zuo=1,you=s,mid;
for(int i=0;i<n;i++)scanf("%d",&sto[i]);
sort(sto,sto+n);
int sg,cnt,ii;
while(zuo!=you)
{
mid=(zuo+you+1)>>1;
sg=cnt=0;
for(ii=0;ii<n;ii++)
{
if(s-sto[ii]<mid)break;
if(sto[ii]-sg<mid)cnt++;
else sg=sto[ii];
}
cnt+=n-ii;
if(cnt<=m)zuo=mid;
else you=mid-1;
}
printf("%d",zuo);
return 0;
}