题目传送门

这道题卡了我十几次提交都没过

我的提交记录

题目大意：

给定一个长度为 $n$ 的字符串，也就是 $n$ 个字符，由 $n$ 和 $1$ 组成，描述牛棚里的牛栏。$0$ 表示空着的牛栏，$1$ 表示有奶牛的牛栏。插入两头奶牛，问你最近的奶牛之间的最大距离。

思路：

最近我一直在打二分，看到了最近的最大就确定了这是二分。先输入 $n$ 个字符，如果为 1 就记录当前的位置。然后就是二分，用一个 check 函数判断一下 $mid$ 的距离可不可行，如果可以，就把 $l$ 的值扩大；否则把 $r$ 的值缩小。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[100005],t,b[100005];
int check(int x)
{
	for(int i=1;i<=t;i++)
	{
		b[i]=a[i];
	}
	int tot=t;
	b[++tot]=1-x;
	b[++tot]=n+x;
	sort(b+1,b+tot+1);
	int ans=0;
	for(int i=1;i<=tot;i++)
	{
		if(b[i]+(x*2)<=b[i+1])
		{
			ans++;	
			if(ans==2)
			{
				return 1;
			}
			else
			{
				b[++tot]=b[i]+x;
				sort(b+1,b+tot+1);
			}
		}
	}
	return 0;
}
signed main()
{
	cin>>n;
	int l=0,r=n;
	a[0]=INT_MIN;
	for(int i=1;i<=n;i++)
	{
		char ch;
		cin>>ch;
		if(ch=='1')
		{	
			a[++t]=i;
			r=min(r,a[t]-a[t-1]);
		}	
	}	
	int ans=-1; 
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid))
		{
			l=mid+1;
			ans=mid;
		}
		else
		{
			r=mid-1;
		}
	}
	cout<<ans;
}