0090.管道.md

90. 管道

题目链接

二分，区间合并

二分寻找第 mid 时刻是否可以全部覆盖水管

每个阀门在第 mid 时刻都会覆盖一小段水管，子段的区间是 [Li - (Ti - Si), Li + (Ti - Si)]

找到每个阀门覆盖的区间后，判断这些区间加起来是否覆盖了全段水管

C

C++

Java

import java.util.*;

public class Main {

    static int MAX = 100010;
    static long LEN;
    static int N;

    static int[] L = new int[MAX];
    static int[] S = new int[MAX];

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        LEN = scan.nextLong();
        for (int i = 0; i < N; i++) {
            L[i] = scan.nextInt();
            S[i] = scan.nextInt();
        }

        int l = 0, r = Integer.MAX_VALUE;
        int ans = -1;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            if (isOk(mid)) {
                // 可以流通
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(ans);
        scan.close();
    }

    
    static boolean isOk(int mid) {
    	int[][] temp = new int[N][2];
    	for (int i = 0; i < N; i++) {
        	if (S[i] <= mid) {
        		// 找到每个阀门可以填充的子段
        		temp[i][0] = L[i] - (mid - S[i]);
        		temp[i][1] = L[i] + (mid - S[i]);
        	}
        }
    	// 根据子段左端点排序
        Arrays.sort(temp, (x, y) -> Integer.compare(x[0], y[0]));
        int left = temp[0][0];
        int right = temp[0][1];
        for (int i = 1; i < temp.length; i++) {
            if (right + 1 < temp[i][0]) {
                break;
            } else {
                right = Math.max(right, temp[i][1]);
            }
        }
        // 判断子段是否覆盖全部水管
        return left <= 1 && right >= LEN;
    }

}

Python

JS

Go