AcWing 1659. 社交距离 I
原题链接
简单
作者:
静静在Coding
,
2022-03-26 16:42:28
,
所有人可见
,
阅读 156
二分 一个区间可以插入多个牛 不能if检查 要用while
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int a[N],m,n;
char s[N];
bool check(int x)
{
int p = 1 - x,cnt = 0;
for(int i = 1;i <= m;i++){
while(p + x + x <= a[i]) cnt++,p += x; // p + x为插入的奶牛 //这里不能写成if
p = a[i];
}
while(p + x <= n) cnt++,p += x; //如果n结尾没有奶牛
return cnt >= 2;
}
int main()
{
cin>>n>>s + 1;
for(int i = 1;i <= n;i++){
if(s[i] == '1') a[++m] = i;
}
int l = 1,r = n;
for(int i = 1;i < m;i++){
r = min(a[i + 1] - a[i],r);
}
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout<<l;
return 0;
}