Acwing 社交距离 分类讨论+贪心

一种新型疾病，COWVID-19，开始在全世界的奶牛之间传播。

Farmer John 正在采取尽可能多的预防措施来防止他的牛群被感染。

Farmer John 的牛棚是一个狭长的建筑物，有一排共 N">N 个牛栏。

有些牛栏里目前有奶牛，有些目前空着。

得知“社交距离”的重要性，Farmer John 希望使得 D">D 尽可能大，其中 D">D 为最近的两个有奶牛的牛栏的距离。

例如，如果牛栏 3">3 和 8">8是最近的有奶牛的牛栏，那么D=5">D=5。

最近两头奶牛新来到 Farmer John 的牛群，他需要决定将她们分配到哪两个之前空着的牛栏。

请求出他如何放置这两头新来的奶牛，使得 D">D 仍然尽可能大。

Farmer John 不能移动任何已有的奶牛；他只想要给新来的奶牛分配牛栏。

输入格式

输入的第一行包含 N">N。

下一行包含一个长为 N">N 的字符串，由0">0 和 1">1 组成，描述牛棚里的牛栏。

0">0 表示空着的牛栏，1">1 表示有奶牛的牛栏。

字符串中包含至少两个 0">0，所以有足够的空间安置两头新来的奶牛。

输出格式

输出 Farmer John 以最优方案在加入两头新来的奶牛后可以达到的最大 D">D 值（最近的有奶牛的牛栏之间的距离）。

D">2≤N≤10^5

D">分析题干：我们先浅浅地分析一下题干，这道题地意思就是我们往标号是0的围栏中放入两头奶牛，然后我要让两头奶牛之间的坐标差D越大越好；

D">一开始我是用了一个比较笨的思路，我考虑两头奶牛是不是要相邻的放，但这样的话考虑到出事的奶牛会有很多种情况，可能在头部，可能在中间有一个，可能一个都没有就需要分太多类了；

D">所以后买你在看题解的时候遇到的这个方法很好，我们可以先通过初始化牛栏数组来得到当前的D，已知加入两头奶牛之后，D不会变大，所以我们可以二分的搜索答案，我们令l = 1 ， r = D，然后取mid，我们看当当前最大的D取到mid时可不可以插入两头牛；

D">所以我就写了一个check函数，我们把每一个已经放了牛的位置放在一个数组里面，我们从第一个数开始看，如果p（当前的位置）满足，p + mid + mid <= a[i]，也就是说我在p后面mid的地方观察能不能放一头牛，也就是会不会和后面一个位置的牛的距离小于mid，如果行就插入并将p往后移动mid位置，重复操作直到不能插入，然后我就将p移动到a[i]上，以此类推；

D">值得注意的是，跳出循环后，p可能在最后一个已经有牛的位置上，他后面全是0，我也要向上面一样去做判断，最后观察我在保证D = mid的情况下能不能插入两头牛以上，能得话我就让ans = mid，然后继续二分直到边界跳出！

D">这样二分答案是非常常见的！

D">代码：

#include
#define maxn 100010

using namespace std;
int n,m,ans = 0;
char str[maxn];
int a[maxn];

bool check(int x){
int p = 1-x , cnt = 0;
for(int i = 1;i<=m;i++){
while(p+x+x<=a[i]) p+=x, cnt++;
p = a[i];
}
while(p+x<=n) p+=x, cnt++;
return cnt>=2;
}

int main()
{
cin >> n;
cin >> str+1;
for(int i = 1;i<=n;i++)
if(str[i] == '1' ) a[++m] = i;
int l = 1 ,r = n;
for(int i=1; i
while(l<=r)
{
int mid = l+r >> 1;
if(check(mid)){
ans = mid;
l = mid+1;
}
else r = mid-1;
}
cout << ans;
return 0;
}