二分答案

二分答案

#include<bits/stdc++.h>
using namespace std;
int L,n,m,a[50009];
bool check(int x){//判断一下能否把跳跃距离拉到x及以上
    int sum=0,cnt=0;//sum表示当前位置，cnt表示移走石头数量
    for(int i=1;i<=n;i++){
        if(L-a[sum]>x&&n-i+1+cnt<=m){
            return true;
        }//洛谷的特殊数据
        if(a[i]-a[sum]>=x){//如果跳跃距离超过x,跳过去
            sum=i;
        }else{
            cnt++;//移走第i个石头
        }
    }
    if(L-a[sum]<x){
        return false;
    }else{
        return cnt<=m;
    }
}
int main(){
    cin>>L>>n>>m;
    for(int i=1;i<=n;i++){
        int sb;
        cin>>sb;
        a[i]=sb;
    }
    //二分
    int l=0,r=1e9;
    while(l<r){
        int mid=(l+r+1)/2;/*右区间最左端点
        int mid=(l+r)/2;  左区间最右端点*/
        if(!check(mid)){
            r=mid-1;
        }else{
            l=mid;   
        }
    }
    cout<<l;
    return 0;
}