蓝桥杯备赛-贪心-管道

问题描述

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

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

对于位于 LiLi​ 的阀门，它流入的水在 TiTi​ (Ti≥SiTi​≥Si​) 时刻会使得从第 Li−(Ti−Si)Li​−(Ti​−Si​) 段到第 Li+(Ti−Si)Li​+(Ti​−Si​) 段的传感器检测到水流。

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

输入格式

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

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

输出格式

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

样例输入

3 10
1 1
6 5
10 2

样例输出

5

评测用例规模与约定

对于 3030% 的评测用例，n≤200n≤200，Si,len≤3000Si​,len≤3000；

对于 7070% 的评测用例，n≤5000n≤5000，Si,len≤105Si​,len≤105；

对于所有评测用例，1≤n≤105​1≤n≤105​，1≤Si,len≤109​1≤Si​,len≤109​，1≤Li≤len​1≤Li​≤len​，Li−1<Li​Li−1​<Li​​。

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;
//二分猜时间+逐一检验是否覆盖整条管道(求每一次开水后的区间，然后排序)
//终于在九点多百分之百通过（哭）
//细节很多，尤其是关于数组，还有
struct boon {//开阀的管道
	int l;
	int s;
};
int n, len;
vector<boon> kai;
bool check(long long t) {//这里要改成long long，保持统一
	vector<pair<long, long>> guanzi;
	long long left;
	long long right;
	for (int i = 1; i <= n; i++) { 
		if (t >= kai[i].s) {
			left  = kai[i].l - (t - kai[i].s);
			right = kai[i].l + (t - kai[i].s);
			guanzi.push_back({ left,right });//注意写法
		}
	}//遍历得到区间
	if (guanzi.size() == 0) return false;//忽略了为空直接跳出
	sort(guanzi.begin(), guanzi.end());//不能+n,可能有的管道没有开，没有被放入
	if (guanzi[0].first > 1) {
		return false;
	}//第一个没灌水直接跳出
	else {
		long long start = guanzi[0].first;
		long long end = guanzi[0].second;
		for (int i = 1; i < guanzi.size(); i++) {//不是n
			if (guanzi[i].first - end>=2) {//[1,3][4,6]是满足的，不能用guanzi[i].first>end
				return false;
			}///有间隙，没重合
			else {
				if (guanzi[i].second > end)
					end = guanzi[i].second;
			}//重合了进行合并
		}
		if (start <= 1 && end >= len){return true;}
		else { return false; }
	}
}
int main() {
	cin >> n >>len;
	kai.resize(n + 2);
	for (int i = 1; i <= n; i++) { cin >> kai[i].l >> kai[i].s; }
	long long ltime = 0;
	long long rtime = INT_MAX;//时间的区间，rtime可以是2e9
	while (ltime < rtime) {
		long long mid = (ltime + rtime) / 2;//long long 防止溢出
		if (check(mid)) {//全覆盖
			rtime = mid;
		}
		else {//未覆盖
			ltime = mid + 1;
		}
	}
	cout << ltime;
	return 0;
}