CF 655c Enduring Exodus
题目描述：小牛带着他的k头牛住旅馆（每头牛和人一间），但是旅馆有些房间已经住了人了，小牛怕有人偷牛，所以选择尽可能靠的近，现在让你输出最优情况的最远距离 (总共n间房子，0表示空，1表示已经有人住了)
(1 ≤ k < n ≤ 100 000)
分析：暴力各个点的情况然后二分找优解的最长距离时间复杂度O(n*log(n))，理解下这里的”单调“
ac代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
int sum[100005];
string s;
cin>>n>>m>>s;
memset(sum,0,sizeof sum);
for(int i=0,sz=s.length();i<sz;i++){
sum[i+1]=sum[i]+(s[i]!='1');
}
int mi=0x3f3f3f3f;
for(int i=0,sz=s.length();i<sz;i++){
if(s[i]=='1')continue;
int l=0,r=sz;
while(l<r){
int mid=(l+r)>>1;
int l1=max(0,i-mid),r1=min(n-1,i+mid);
if(sum[r1+1]-sum[l1]>=m+1) r=mid;
else l=mid+1;
}
mi=min(mi,l);
}
cout<<mi<<endl;
}
投递哔哩哔哩等公司9个岗位
