P3853路标设置

思路：
最优解——二分答案
空旷指数增加，增设路标数量变少(单调减)
向左找
check检查在当前空旷指数mid之下，所需要增设路标的个数是否<=K

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int L,N,K,lft,rgt,mid,a[MAXN]; bool check(int x)
{int lst=0,cnt=0,dist=0;//distancefor(int i=1;i<=N;++i){dist=a[i]-a[lst];if(dist>x){cnt+=dist/x;//如果要加 则可能多加if(dist%x==0) cnt--; }lst=i;}return cnt<=K;
}int main()
{cin>>L>>N>>K;for(int i=1;i<=N;++i)scanf("%d",&a[i]);lft=1,rgt=L;while(lft<rgt){//向左找 mid=(lft+rgt)/2;if(check(mid)){rgt=mid;}else{lft=mid+1;}} cout<<lft;return 0;
}