A33083题解（二分答案）

#include<bits/stdc++.h>
using namespace std;
int d[100005];
int l,n,k,x,lf,rg=10000005;
bool check(int h){
    int add=0;
    for(int i=1;i<=n;i++){
        if(d[i]-d[i-1]>h){
            add+=(d[i]-d[i-1]-1)/h;
        }
    }
    return add<=k;
}
int main(){
    cin>>l>>n>>k;
    d[0]=0;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(x==0){i--;n--;}
        d[i]=x;
    }
    if(d[n]!=l){d[++n]=l;}
    while(lf<rg){
        int mid=(lf+rg)/2;
        if(check(mid)){
            rg=mid;
        }
        else{
            lf=mid+1;
        }
    }
    cout<<lf;
    return 0;
}