题目描述

解题思路

这个题目意思很拗口，其实理解一下几点就好：

  1. 每个阀门都是会放水的，向两边放水。
  2. 中间如果有一个阀门没有打开是不会阻隔水的，也就是说我们只要开放了一个闸门，只要等总会流过所有管道。

我们可以发现len是1e9数量级，n是1e5数量级。这个题目需要求的是最小的t我们t最小是si的最小值，最大是len。暴力做法就是枚举t，然后每个t用一下区间合并O(nlogn)看下是否流过所有管道。因此暴力的时间复杂度是O(1e5log1e5*1e9)。肯定超时了，但是我们发现我们t视具有单调性的，我们可以用二分枚举这个t，最后时间复杂度就是O(1e5*log1e5*log1e9)。

回忆一下区间合并思路
我们数组维护每一个区间的左端点和右端点，根据左端点排序，从左往右枚举每个区间，但凡相邻两个区间不能合并，那么就合并失败了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.io.*;
import java.util.*;

class Main{
    public static int N = 100010,n,len,m_in;
    public static int[] s = new int[N],l = new int[N];
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //判断i时刻能不能流过所有的传感器
    public static boolean check(int t){
        Pair[] seg = new Pair[N];
        int j = 1;
        //区间合并
        for(int i = 1;i <= n;i++)
            if(t >= s[i])
                seg[j++] = new Pair(Math.max(1,l[i] - (t -s[i])),Math.min(len,l[i] + (t - s[i])));

        Arrays.sort(seg,1,j,new Comparator<Pair>(){
            public int compare(Pair o1,Pair o2){
                if(o1.l == o2.l) return o1.r - o2.r;
                if(o1.l < o2.l) return -1;
                else return 1;
            }
        });
        if(j == 1 ||seg[1].l > 1) return false;
        int r = seg[1].r;
        for(int i = 2;i < j;i++){
            //如果后面的左端点和前面的右端点不重合那肯定就不行
            if(seg[i].l - r >= 2) return false;
            if(seg[i].r > r) r = seg[i].r;
        }
        if(r != len) return false;

        return true;
    }

    public static void main(String[] args)throws Exception{
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);len = Integer.parseInt(s1[1]);
        int sm = (int)1e9;
        for(int i = 1;i <= n;i++){
            String[] s2 = br.readLine().split(" ");
            l[i] = Integer.parseInt(s2[0]);
            s[i] = Integer.parseInt(s2[1]);
            sm = Math.min(sm,s[i]);
        }

        int res = 0;
        long l = sm,r = sm+len;
        while(l < r){
            int mid = (int)((l + r) / 2);
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        System.out.print(l);
    }
    static class Pair{
        int l,r;
        public Pair(int l,int r){
            this.l = l;
            this.r = r;
        }
    }
}