2024/3/11打卡管道(14届蓝桥杯省赛)——二分+区间合并

目录

题目

思路

代码

---

题目

有一根长度为 len 的横向的管道，该管道按照单位长度分为 len 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。

一开始管道是空的，位于 Li 的阀门会在  时刻打开，并不断让水流入管道。

对于位于  的阀门，它流入的水在 时刻会使得从第 段到第  段的传感器检测到水流。

求管道中每一段中间的传感器都检测到有水流的最早时间。

输入格式

输入的第一行包含两个整数 n,len，用一个空格分隔，分别表示会打开的阀门数和管道长度。

接下来 n 行每行包含两个整数 ,，用一个空格分隔，表示位于第  段管道中央的阀门会在  时刻打开。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 30%30% 的评测用例，n≤200，Si,len≤3000；
对于 70%70% 的评测用例，n≤5000，Si,len≤10^5；
对于所有评测用例，1≤n≤10^5，1≤Si,len≤10^9，1≤Li≤len，Li−1

输入样例：

3 10
1 1
6 5
10 2

输出样例：

5

 

思路

        通过题意可以发现，假如说在  时刻满足题目要求，那么比  大的时刻，管道被覆盖的范围也一定大于等于  时刻的，一定满足要求，故具有单调性，此时可以想到用二分来做。

如何确定一个时刻  所经过的长度是多少？我们通过      可以来确定一个阀门被打开后所流过的长度。 即为左边能流到的最远的位置，即为右边流到最远的位置。

获取到  时刻每一个被打开阀门的水流过的区间后，如何合并所有的区间，判断是否将管道覆盖完全？此时可以想到区间合并的做法。将所有的区间合并起来，看是否覆盖完管道。

        区间合并：区间合并算法-CSDN博客

代码

注：此题的区间合并并不是两个区间有交集才能合并，例如[1, 2]和[3, 4]也可以进行合并成[1, 4]

注意以为r取到了2e9，再进行区间相加，可能或爆int

// 在 x 的时间内能否完成所有传感器检测到水流
// 在 x 时刻，每个能被打开的阀门被打开后，会有一段区间，那我们合并这段区间，判断是否能从0,覆盖到len
 
import java.io.*;
import java.util.*;
 
class Main{
    static int N = 100010;
    static int n,len;
    static int[] l = new int[N]; // 阀门位置
    static int[] s = new int[N]; // 阀门打开时间
    static Queue q = new PriorityQueue<>(); // 存储区间，按左端点排序
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] str = in.readLine().split(" ");
        n   = Integer.parseInt(str[0]);
        len = Integer.parseInt(str[1]);
        for(int i=1;i<=n;i++){
            str = in.readLine().split(" ");
            l[i] = Integer.parseInt(str[0]);
            s[i] = Integer.parseInt(str[1]);
        }
        
        // 进行二分，找最小时间
        long l = 0, r = 2000000000; // r需要取到2000000000，因为存在 1 1000000000
                                    //                               1000000000 1000000000 这种情况，那么时间就需要1999999999
        while(l
            long mid = l+r>>1;
            if(check(mid)) r = mid; //当前mid时段可以满足
            else l = mid+1;
        }
        
        System.out.println(r);
    }
    public static boolean check(long u){
        // 获取所有的区间
        for(int i=1;i<=n;i++){
            long t = u-s[i];
            if(t>=0){ // u时间大于等于打开的时间
                long x = l[i]-t;
                long y = l[i]+t;
                q.add(new PII(x,y));
            }
        }
        
        // 对所有区间进行合并        
        long st = 0, ed = 0;
        while(!q.isEmpty()){
            PII i = q.poll();
            long x = i.l;
            long y = i.r;
            if(x<=ed+1){
                ed = Math.max(ed,y);
            }
            else return false;
        }
        if(edreturn false;
        else return true;
    }
}
class PII implements Comparable{ // 存储当前时间段被覆盖的区间
    long l;
    long r;
    public PII(long l,long r){
        this.l = l;
        this.r = r;
    }
    
    public int compareTo(PII i){
        return this.l-i.l>0?1:-1;
    }
}