管道（二分+区间合并）

题目描述

有一根长为len的管道，被分成len段，每一段中间有一个阀门，位于$L_i的阀门会在S_i时刻打开$，水流入管道，当$T_i时刻时(T_i \ge S_i)，$水会向左边蔓延$L_i - (T_i - S_i)个单位，同时向右边蔓延L_i + (T_I - S_i)$，求水覆盖整个管道的最早时间。

数据范围

$1 \le n \le 10^5,$

输入样例

5
1 2
2 4
5 6
7 8
7 9

输出样例

3

思路分析

1、由题意可知，一定存在一个时刻，使得在这个时刻之前所有的管道没有被水覆盖，而在这个时刻之后，所有的管道全部被水覆盖，所以这个题目具有二段性，可以是用二分来搜索这个零界点。
2、二分的判断条件是所有水管已经被水覆盖，此处可以用到区间合并，只要判断合并后的区间长度等于len,则可以在mid的左边寻找正确答案，否则答案在mid右边。

算法1

$O(nlogn)$

import java.util.*;
import java.lang.*;
class Main{
    static int n;
    static int len;
    static List<int[]> valve = new ArrayList<>();

    //区间合并
    public static boolean detec(int T){
        List<Pair> list = new ArrayList<>();
        //生成区间
        for(int[] v : valve){
            int Li = v[0];
            int Si = v[1];
            if(Si <= T){
                int t = T - Si;
                int l = (int)Math.max(1, (long)Li - t);
                int r = (int)Math.min(len, (long)Li + t); 
                list.add(new Pair(l, r));
            }
        }        

        Collections.sort(list);


        //区间合并
        //操作区间
        int st = -1;
        int ed = -1;
        int rs = 0;

        for(Pair item : list){
            if(item.getX() > ed + 1){
                if(ed != -1){
                   rs += ed - st + 1; 
                }
                st = item.getX();
                ed = item.getY();
            }else{
                ed = Math.max(item.getY(), ed);
            }
        }

        if(ed != -1){
            rs += ed - st + 1; 
        }

        if(rs == len){
            return true;
        }else{
            return false;
        }
    }

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

        //将位置、时间数组存入集合        
        for(int i = 0; i < n; i++){
            int position = sc.nextInt();
            int time = sc.nextInt();
            valve.add(new int[]{position, time});
        }

        //二分去搜索一个正好能够使水管全部覆盖的时刻(时刻最大值为2e9)
        long l = 0;
        long r = (long)2e9;
        while(l < r){
            long mid = l + r >> 1;
            if(detec((int)mid))  r = mid;
            else    l = mid + 1;
        }

        System.out.print(l);
    }
}

class Pair implements Comparable<Pair>{
    private int x;
    private int y;

    public Pair(int x, int y){
        this.x = x;
        this.y = y;
    }

    public int getX(){
        return x;
    }

    public int getY(){
        return y;
    }

    @Override
    public int compareTo(Pair o){
        if(this.x - o.x == 0){
            return this.y - o.y;
        }
        return this.x - o.x;
    }

    @Override
    public String toString(){
        return x + " " + y;
    }
}

时间复杂度分析

1、二分查找的时间复杂是O(logn)，由于log(2e9) $\approx$ 31，所以二分查找最多查找31次。
2、生成区间时间复杂度是O(n)，主要是遍历集合耗时。
3、排序耗时O(nlogn)
4、区间合并复杂度o(n)

注意

1、要对mid、Li - T + Si、Li + T - Si进行处理，否则会int溢出