AcWing 5407. 管道(Python3)
原题链接
中等
作者:
跂未
,
2024-03-05 15:45:42
,
所有人可见
,
阅读 60
n, m = map(int, input().split())
tupe = []
for _ in range(n):
l, s = map(int, input().split())
tupe.append((l, s))
def check(t):
# 存储区间
seg = []
# 遍历tupe获得区间段
for l, s in tupe:
if s > t:
continue
left = max(1, l - (t - s))
right = min(m, l + (t - s))
seg.append((left, right))
seg.sort()
# 判断区间开头是否等于1
if seg[0][0] > 1:
return False
dr = seg[0][1]
# 循环遍历跟新dr
for i in range(1, len(seg)):
if seg[i][0] > dr + 1:
return False
dr = max(dr, seg[i][1])
# 判断区间结尾是否等于m
if dr == m:
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))
这个题解还是比较清晰的