P10909 [藍橋杯 2024 國 B] 立定跳遠 - 洛谷

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef long long ll;
typedef pair<int,int> pii;
int n,m;
int a[N];
int an;
bool check(int l)
{int pos=0;int c=1;int w=m;for(int i=1;i<=n;i++){if(a[i]-pos<=l){pos=a[i];continue;}if(a[i]-pos>l){if(a[i]-pos<=2*l&&c==1){pos=a[i];c--;continue;}else{int e=(a[i]-pos)/l-1;if((e+1)*l==a[i]-pos);else e++;w-=e;if(w<0) return false;pos=a[i];    }}}return true;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];int l=0,r=INT_MAX;while(l<=r){int mid=(l+r)>>1;if(check(mid)){r=mid-1;an=mid;}else l=mid+1;}cout<<an;return 0;
}