代码如下,一个测试点也没过,实在看不出来哪错了QAQ。
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
ll l,n,k;
ll arr[100000+10];//存每个路标的位置
bool judge(ll x)//函数用于判断 以x作为空旷指数 是否可行
{
ll cnt = 0;//用于统计放入路标个数
for(int i=1; i<=n+1; i++)//判断每个区间是否需要放入路标,若需要,则计算路标个数
{
if(arr[i]-arr[i-1]<=x)continue;//不用放路标
else//需要放路标,计算 放入的路标个数
{
for(int j=2; j<=k+1; j++)//把j当除数,j-1就是放入i与i-1区间的路标个数
{
if((arr[i]-arr[i-1])%j==0 && (arr[i]-arr[i-1])/j<=x)
{
cnt+=j-1;
break;
}
else if((arr[i]-arr[i-1])%j!=0 && (arr[i]-arr[i-1])/j +1<=x )
{
cnt+=j-1;
break;
}
}
}
}
if(cnt==k)return 1;
return 0;
}
int main()
{
cin>>l>>n>>k;
arr[0]=0;//起点坐标初始化
arr[n+1]=l;//终点坐标初始化
for(int i=1; i<=n; i++)//读入数据
scanf("%lld",&arr[i]);
//二分答案
ll left = 0 , right = l;
while(left<=right)
{
ll mid = (left + right)/2;
if(judge(mid))
right = mid - 1;
else
left = mid + 1;
}
cout<<right+1;
return 0;
}