一次性AC,我处理了一个特判:见下,last是存最后一个合理的石头的下标,n不能忘了加1,且要在主函数加。
#include<iostream>
using namespace std;
const int N=5e4+10;
int a[N],l_jl,n,m;
bool check(int mid)
{
int js=0;//存移走石头的数量
int last=0;//存最后一个合理的石头的下标
//循环中我处理了一个特例:i指向终点,
//且last指向的石头与i指向的终点之间的
//距离<mid,实际移走的石头last指向的石头。
for(int i=1;i<=n;i++)
{
if(a[i]-a[last]>=mid)
last=i;
else
js++;
}
if(js<=m)
return true;
else
return false;
}
int main()
{
// freopen("xxx.in","r",stdin);
// freopen("yyy.out","w",stdout);
cin >> l_jl >> n >> m;
for(int i=1;i<=n;i++)
cin >> a[i];
a[n+1]=l_jl;
n++;
int l=1,r=l_jl;
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid))
l=mid;
else
r=mid-1;
}
cout << l;
// fclose(stdin);
// fclose(stdout);
return 0;
}