算法

二分

时间复杂度

$lg(L)*n$

C++ 代码

#include <iostream>
#include <vector>
using namespace std;
int stone[50010],L,n,m;
bool check(int k){
    int cnt=0;
    vector<bool> f(500010);
    for(int i=1,l=0;i<=n;++i){
        if(stone[i]-l<k){
            cnt++;
            f[i]=1;
        }
        else l=stone[i];
    }
    for (int i=n,l=L;i>=1;--i){
        if(f[i]) continue;
        if(l-stone[i]<k){
            cnt++;
        }
        else l=stone[i];
    }
    return cnt<=m;
}
int main(){
    cin>>L>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>stone[i];
    }
    int l=0,r=L,ans;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)) l=mid+1,ans=mid;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}