Social Distancing I

题目描述

一种可怕的新疾病 COWVID-19 开始在全球的奶牛中传播。 Farmer John 正在尽可能采取各种预防措施，以保护他的牛群免受感染。

Farmer John 的牛棚是一座又长又窄的建筑，里面有一排共 $N$ 个牛栏（$2 \leq N \leq 10^5$）。其中一些牛栏目前被奶牛占据，另一些为空。由于了解到“保持社交距离”的重要性，Farmer John 想要最大化 $D$，其中 $D$ 是任意两头占据牛栏的奶牛之间的最小距离。比如，如果第 3 个和第 8 个牛栏是距离最近且都被占据的牛栏，那么 $D = 5$。

最近有两头新奶牛加入了 Farmer John 的牛群，他需要决定把她们分配到哪些原本空着的牛栏中。请确定他应如何放置这两头新奶牛，使得最终的 $D$ 仍然尽可能大。Farmer John 不能移动任何已有的奶牛；他只想为新奶牛分配牛栏。

输入格式

第一行输入包含 $N$。 第二行包含一个长度为 $N$、由 0 和 1 构成的字符串，描述牛棚中牛栏的占用情况。0 表示空牛栏，1 表示已被占据的牛栏。该字符串至少包含两个 0，因此至少有足够的空间容纳两头新奶牛。

输出格式

请输出一个整数：在以最优方式加入两头新奶牛之后，Farmer John 能达到的最大 $D$ 值（即任意两头占据牛栏的奶牛之间的最小距离）。

14
10001001000010

2

提示

在这个例子中，Farmer John 可以添加奶牛，使得占用字符串看起来像 10x010010x0010，其中 x 表示新加入的奶牛。此时 $D = 2$。不可能通过其他添加方式得到更大的 $D$。

评分： 测试点 2-6 满足 $N\le 10$。 测试点 7-8 满足 $N\le 100$。 测试点 9-11 满足 $N \le 5000$。 测试点 12-15 无额外限制。 题目来源：Brian Dean

标签: USACO|2020|Bronze

来源

USACO|2020|Bronze