AcWing 3973. 无线网络(Python3)
原题链接
困难
作者:
跂未
,
2024-03-05 08:04:08
,
所有人可见
,
阅读 25
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def check(mid):
j = 0
for i in range(n):
# 遍历找到距离大于牛的最近的基站
while j + 1 < m and b[j + 1] <= a[i]:
j += 1
# 如果距离小于牛的最近的基站和距离大于牛的基站的范围
# 都不能覆盖牛那么返回False
if abs(a[i] - b[j]) > mid:
if j + 1 >= m or (b[j + 1] - a[i]) > mid:
return False
return True
l, r = 0, 2e9
# 二分覆盖范围
while l < r:
mid = (l + r) // 2
if check(mid):
r = mid
else:
l = mid + 1
print(int(r))