蓝桥杯[每日一题] 真题：管道(java版)

题目描述

有一根长度为 len 的横向的管道，该管道按照单位长度分为 len 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。一开始管道是空的，位于 Li 的阀门会在 Si 时刻打开，并不断让水流入管道。 对于位于 Li 的阀门，它流入的水在 Ti (Ti ≥ Si) 时刻会使得从第 Li−(Ti−Si) 段到第 Li + (Ti − Si) 段的传感器检测到水流。 求管道中每一段中间的传感器都检测到有水流的最早时间。

输入格式

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

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

输出格式

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

样例输入

3 10
1 1
6 5
10 2

样例输出

5

评测用例规模 

解题思路

这一道题是典型的二分题目，框架和之前讲的冶炼金属是类似的，但关键就在于check函数怎么写。

在这道题目中，check函数就是一个区间覆盖问题，要判断子区间是否覆盖了原区间。我刚开始想的是，只要前一个的右端点大于等于后一个的左端点，一个一个比，最后能到达末尾就表示覆盖完了区间。这种我感觉不太好写，而且我觉得多多少少有些不对。有人这样写过吗，欢迎在评论区留言！

于是我又去看题解了，发现其实这种思路也挺不错的：按照区间的左端点进行排序，然后一步步拼接区间。有两个关键点：拼不上的情况--上一个区间的右端点加上1还达不到下一个区间的左端点；然后就是能拼上的情况了。但是我写的时候犯了一个错误，我写的判定条件是上一个区间的右端点大于等于下一个区间的左端点。之后画图分析我才发现，如果right是5，下一个区间的左端点是6，这样就会误判为拼不上，但实际是能够拼的。

附上我思考的时候画的图

代码实现 

import java.io.*;
import java.util.Arrays;

public class Main {
	private static int n;
	private static int len;

	public static void main(String[] args) throws IOException {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		len = scan.nextInt();
		int[][] record = new int[n][2];
		int l = 0, r = 1000000010;//为什么取这么大？取太小过不了全部用例
		for (int i = 0; i < n; i++) {
			record[i][0] = scan.nextInt();
			record[i][1] = scan.nextInt();
		}
		while (l < r) {
			int mid = l + r >> 1;
			if (check(mid, record))
				r = mid;
			else
				l = mid + 1;
		}
		System.out.println(l);
	}

	private static boolean check(int T, int[][] record) {
		// 先初始化区间数组
		int[][] temp = new int[record.length][2];
		for (int i = 0; i < record.length; i++) {
			if (T >= record[i][1]) {
				temp[i][0] = record[i][0] - (T - record[i][1]);
				temp[i][1] = record[i][0] + (T - record[i][1]);
			}

		}
		// 合并区间
		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;
	}
}


class Scanner {
	private BufferedReader bf;
	private StreamTokenizer st;

	public Scanner(InputStream inputStream) {
		this.bf = new BufferedReader(new InputStreamReader(inputStream));
		this.st = new StreamTokenizer(bf);
	}
	public int nextInt() throws IOException {
		st.nextToken();
		return (int)st.nval;
	}
	public String nextLine() throws IOException {
		return bf.readLine();
	}
}