二分找时间m
区间合并check判断在当前时间m下,管道有没有被灌满
最终找到第一个使得管道被灌满的时间,即最小的时间
Python 代码
from copy import deepcopy
n,leng = map(int,input().split())
# st = [0 for _ in range(leng+1)]
# st[0] = 1
ops = []
for i in range(n):
tmp = list(map(int,input().split()))
ops.append(tmp)
# def check(m):
# tmp_st = deepcopy(st)
# for item in ops:
# if m >= item[1]:
# left = max(1,item[0]-(m-item[1]))
# right = min(leng,item[0]+(m-item[1]))
# tmp_st[left:right+1] = [1]*(right - left + 1) # 切片赋值太耗时,改成区间合并
# #而且当管道leng很长时,st会爆内存
# return not tmp_st.count(0)
def check(m):
area = []
for item in ops:
if m >= item[1]:
left = max(1,item[0]-(m-item[1]))
right = min(leng,item[0]+(m-item[1]))
area.append([left,right])
area = sorted(area,lambda x:x[0]) # 将按照区间的左端点大小完成从小到大的排序
#将区间合并,并判断是不是区间覆盖了整个管道
start,end = -1,-1
for i in range(len(area)):
if area[i][0] <= end+1:
end = max(end,area[i][1])
#start肯定是比area[i][0]小的
else:
start,end = area[i][0],area[i][1]
if start==1 and end==leng:
return True
return False
# l, r = 1,leng
# 这是时间的左端点和右端点,最差清空是在1e9时刻只打开惟一一个处于边界的阀门,然后经过1e9灌满管道
l, r = 0,int(2e9)
while l<r:
mid = l+r >> 1
if check(mid):
r = mid
else:
l = mid+1
print(l)
# ops = sorted(ops,lambda x:x[1])
# print(ops)