摘要
Title: 1659. 社交距离 I
Tag: 二分
Memory Limit: 64 MB
Time Limit: 1000 ms

1659. 社交距离 I

题意

一种新型疾病，COWVID-19，开始在全世界的奶牛之间传播。
Farmer John 正在采取尽可能多的预防措施来防止他的牛群被感染。
Farmer John 的牛棚是一个狭长的建筑物，有一排共 N 个牛栏。
有些牛栏里目前有奶牛，有些目前空着。
得知“社交距离”的重要性，Farmer John 希望使得 D 尽可能大，其中 D 为最近的两个有奶牛的牛栏的距离。
例如，如果牛栏 3 和 8 是最近的有奶牛的牛栏，那么 D=5。
最近两头奶牛新来到 Farmer John 的牛群，他需要决定将她们分配到哪两个之前空着的牛栏。
请求出他如何放置这两头新来的奶牛，使得 D 仍然尽可能大。
Farmer John 不能移动任何已有的奶牛；他只想要给新来的奶牛分配牛栏
思路

核心思路就是，二分距离D，能成立的的条件，就是这个0距离前面1和距离后面1的距离都大于等于D
实现：
- 处理next数组， $next[i]$ 用来表示离这个0最近的右边1的下标
- 找到二分上界，即现有的奶牛中，1和1之间的最近距离
- 二分D即可
  - 二分时动态记录一个pre, 代表上一个离得最近的1的位置

代码

'''
Author: NEFU AB-IN
Date: 2022-03-23 17:01:00
FilePath: \ACM\Acwing\1659.py
LastEditTime: 2022-03-23 21:10:19
'''
N = int(1e5 + 10)
nxt = [0] * N
INF = int(2e9)


def check(x):
    cnt = 0
    i, id = 0, -INF
    while i < n:
        if a[i] == 0 and i - id >= x and nxt[i] - i >= x:
            cnt += 1
            id = i
        if a[i] == 1:
            id = i
        i += 1
    return cnt >= 2


n = int(input())
a = list(map(int, input()))

#求next数组，即0的下一个1在哪
id = INF
for i in range(n - 1, -1, -1):
    if a[i] == 0:
        nxt[i] = id
    else:
        id = i

#求1之间的最小距离，也就是二分上界
id = -INF
r = n - 1
for i in range(n):
    if a[i] == 1:
        if id != -INF:
            r = min(r, i - id)
        id = i
# 二分D
l = 1
while l < r:
    mid = l + r + 1 >> 1
    if check(mid):
        l = mid
    else:
        r = mid - 1
print(r)

1659. 社交距离 I

题意

思路

代码