8 3 1
2
4
7
这是hack点数据
这是我的代码
#include <bits/stdc++.h>
using namespace std;
const int N=5e4+100;
int lf,n,m,st[N],tmp[N];
bool chk(int t){
int num=0;
for(int i=0;i<n;i++) tmp[i]=st[i]-(i!=0?st[i-1]:0);
tmp[n]=lf-st[n-1];
for(int i=0;i<=n;i++){
if(tmp[i]<t){
num++;
tmp[i+1]+=tmp[i];
}
if(num>m){
return 0;
}
}
return 1;
}
int main(){
cin >> lf >> n >> m;
for(int i=0;i<n;i++){
cin >> st[i];
}
sort(st,st+n);
int l=0,r=lf;
while(l<r){
int mid=(l+r+1)>>1;
if(chk(mid)) l=mid;
else r=mid-1;
}
cout << l;
return 0;
}
这是正确的。我的错误原因是上面的
tmp[n]=lf-st[n-1];
之前写成了
tmp[n]=lf;
也就是没有减掉最后一个端点导致最后一块石头到终点位置错误,仅供参考