题目描述

二分+区间合并
可能会爆int,注意用long
left = 1;最低就是1时刻

样例

import java.util.*;

/*
   二分思想：
      对检测到有水流的最早时间进行二分，长度为1e9, 假设在最右端点，最长时间为2e9,所以就有可能爆int,用long
*/

/*
   区间合并：
       左端点和右端点相邻，注意这里不是重合，其实就是 左+1 = 右

*/

public class Main {
    static int N = 100010;
    static class Pair {
        int index, second;

        Pair(int index, int second) {
            this.index = index;
            this.second = second;
        }
    }

    static Pair[] a = new Pair[N];
    static int n, len;

    static boolean check(long x) {
        List<Pair> segs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int l = a[i].index, s = a[i].second;

            //如果当前时间，阀门还没开，就跳过
            if (s > x) continue;

            //利用题目给的公式
            int left = Math.max(1, l - (int)x + s);//最左边不能低于1
            int right = Math.min(len, l + (int)x - s);//最右边不能高于length
            segs.add(new Pair(left, right));
        }

        //进行排序，按阀门编号升序排序
        //Collections.sort(segs, Comparator.comparingInt(p -> p.index));
        //segs.sort(Comparator.comparingInt(p -> p.index));
        segs.sort((p1, p2) -> p1.index - p2.index);
        //Collections.sort(segs, (p1, p2) -> p1.index - p2.index);//p1-p2是升序,升序才可写成上面的简写
        //Collections.sort(segs, (p1, p2) -> p2.index - p1.index);//,p2-p1是降序,降序没简写

       //如果没阀门开，也就是时间太小 return false
        if (segs.isEmpty()) return false;

        //如果区间起点不是1 直接return false
        if (segs.get(0).index > 1) return false;

        //第一个阀门的右端点
        int dr = segs.get(0).second;
        for (int i = 1; i < segs.size(); i++) {
            //如果当前阀门的左端点不是和前一个阀门的右端点相邻 说明时间太短 return false
            if (segs.get(i).index > dr + 1) return false;
            //区间合并 把右端点扩大 
            dr = Math.max(dr, segs.get(i).second);
        }

       //看是否 刚好等于len
        return dr == len;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        len = scanner.nextInt();


        for (int i = 0; i < n; i++) {
            int l = scanner.nextInt();
            int s = scanner.nextInt();
            a[i] = new Pair(l, s);
        }

        long l = 1, r = 2000000000;
        while (l < r) {
            long mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }

        System.out.println(l);
        scanner.close();
    }
}