今日学习：二分

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;//目前的路标数blockint space=0;//目前的空旷指数spacefor(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;
}