• 把题目翻译成人话
  • 在一条数轴上给定起点0和终点L
  • 起点和终点之间有N个点，你可以删掉M个点
  • 使得删除后，相邻点之间的距离d的最小值最大
  • 看案例L=25 N=5 M=2
  • N个点坐标 2 11 14 17 21
  • 加上起点和终点0 2 11 14 17 21 25
  • 相邻点之间的距离分别为 2 9 3 3 4 4 最小的d是2
  • 删除2和14后 0 11 17 21 25
  • 相邻点之间的距离分别为 11 6 4 4 最小的d是4
  • 此时d最大，这就是题目的意思求最小的d的最大值
  • 我们不难发现，最大的d一定满足d<=a[i]-a[i-1]
  • 如果d>a[i]-a[i-1]，就移除石头
  • 统计移除的石头数量cnt，cnt<=M就是一个合法答案
  • 利用check二分答案得到最大的d即可
  • 代码11行是剪枝，cnt>M时直接返回false
  • 别忘了终点也有一块石头，13行是判断终点的
#include<bits/stdc++.h>
using namespace std;
int a[50005];
int L,N,M;
bool check(int mid) {
    int cnt = 0; // 移除的石头数
    int last = 0; // 上一个石头的位置，初始是起点
    for(int i=1; i<=N; i++) {
        if(a[i] - last < mid) cnt++;
        else last = a[i];//更新上一块石头的位置  
        if(cnt>M)return false;
    }
    if(L - last < mid) return false;
    return cnt <= M;
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>L>>N>>M;
    for(int i=1;i<=N;i++)cin>>a[i];
    int mn=1,mx=L;
    int l=mn,r=mx,ans=0;
    while(l<=r){
        int mid = l + (r-l) / 2;
        if(check(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans<<'\n';
    return 0;
}