```
#include<iostream>
#include<cstring>
using namespace std;
const int N = 5e4+100;
/*
题目分析：
考虑朴素算法：
即统计从n快石头中选择m快石头删去，时间复杂度为 c(n,m)
再统计每种情况下的最短距离，复杂度为O(n)
最终时间复杂度为显然大于O(N^2) 显然超时
可以枚举最短的距离，通过最短距离反推需要移动的石头数量
如果需要的石头数量>m,说明距离此距离太大,应该让距离小一些 r = mid - 1
如果需要的石头数量<=m,说明距离太小了，应该让距离尽可能的大一些 ans = mid l = mid + 1,ans记录可能的答案
这样时间复杂度为O(nlogn)
*/
int f[N],bac[N],dis[N];
int l,n,m;
int check(int u){
int cnt = 0;
memcpy(bac,dis,sizeof(dis));
for (int i=2;i<=n+2;i++){
if (bac[i]<u){
cnt++;
bac[i+1]+=bac[i];
}
}
return cnt;
}
int main(){
scanf("%d%d%d",&l,&n,&m);
f[1] = 0;
for (int i=2;i<=n+1;i++){
scanf("%d",&f[i]);
}
f[n+2] = l;
for (int i=2;i<=n+2;i++){
dis[i] = f[i]-f[i-1]; //记录与前一点的距离
}
int l = 1,r = 1e9,ans = -1;
while (l<=r){
int mid = (l+r)>>1;
if (check(mid)>m){
r = mid - 1;
}else{
ans = mid;
l = mid + 1;
}
}
cout<<ans<<endl;
return 0;
}
```
by Lawliet142857 @ 2023-03-20 01:35:31