P3853 天津省選

/*
這個題和P2678幾乎一樣，但說實話我還沒看懂。
1.首先檢查的標準我沒想到。是要檢查當前的空曠指數還是路標數？
2.其次check的邏輯我還是沒想明白。
3.犯了個小錯。計算mid應該放在while循環里面。
*/
#include<bits/stdc++.h>
using namespace std;
int length,n,k,ans;
int a[114514];
int l,r,mid;//mid嘗試的空曠指數

bool check(int x){//x當前嘗試的空曠指數
    int block=0;//目前的路標數block
    int space=0;//目前的空曠指數space
    for(int i=1;i<n;i++){
        space=a[i+1]-a[i];
        if (space>=x){
            block+=(space-1)/x;
        }
    }
    return block<=k;
}

int main(){
    cin>>length>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    
    l=1;r=length;
    
    while(l<=r)
    {
        mid=(l+r)/2;
        if (check(mid)){
            r=mid-1;
            ans=mid;
        }
        else{
            l=mid+1;
        }
    }
    cout<<ans;
    return 0;
}