AcWing--管道--＞二分，区间合并

5407. 管道 - AcWing题库

def check(mid):
    q=[]
    # 枚举每一个区间
    for i in range(n):
        L, S = w[i][0], w[i][1]
        if S <= mid:
            t = mid - S
            l = max(1, L - t)
            r = min(m, L + t)
            q.append([l, r])

    # 区间合并
    q.sort()
    st = -1
    ed = -1
    for i in range(len(q)):
        if q[i][0] > ed + 1:
            st = q[i][0]
            ed = q[i][1]
        else:
            ed = max(ed, q[i][1])
    return (st == 1 and ed == m)


# 输入
n, m = map(int, input().split())
 # 存放区间
w = []  #
for i in range(n):
    tmp = list(map(int, input().split()))
    w.append(tmp)
# 二分
l = 0
r =2*10**9
while l < r:
    mid = (l + r) // 2
    if check(mid):
        r = mid
        # print(r)
    else:
        l = mid + 1

print(r)