AcWing 1660. 社交距离 II
原题链接
简单
作者:
人间失格_1
,
2022-02-15 21:33:33
,
所有人可见
,
阅读 189
算法思路
先寻找到可能的最大半径的范围:该半径的边界(取不到)为,没有感染的牛与旁边感染的牛之间的距离的最小值
然后用该半径值带入进行计算,若当前牛感染了,但是前一个牛没有感染,ans+1;当前牛感染前一个牛也感染,但是他们之间间隔大于等于r,则ans+1 最后的ans即为结果
Python3 代码
n = int(input())
ls = [[-1e9,0]]
vis = []
for _ in range(n):
x , y = map(int , input().split())
ls.append([x , y])
ls.sort()
r = 1e9
for i in range(1,n+1):
if ls[i-1][1] ^ ls[i][1]:
r = min(r , ls[i][0] - ls[i-1][0])
ans = 0
for i in range(1 , n + 1):
if (not ls[i-1][1] and ls[i][1] ) or (ls[i][1] and ls[i-1][1] and ls[i-1][0] + r <= ls[i][0]):
ans += 1
print(ans)