5407.管道 (二分+区间合并)

2024-01-03 16:29:54

本题链接:5407. 管道 - AcWing题库

题目:

样例:

输入
3 10
1 1
6 5
10 2

输出
5

思路:

? ? ? ? 根据题目意思,给出 n 个阀门,其中 管道有 len 段,随后 n 个阀门对应的位置在? L?点,并且当 S 时刻阀门的水会放开, 其中 放开后??水在 T_{i}T_{i}?≥?S_{i})时刻会使得从第 L_{i}?? (?T_{i}???S_{i}?) 段到第 L_{i}?+ (?T_{i}???S_{i}?) 段的传感器检测到水流。

? ? ? ? 问输出 全部段点感应到水流的 最早时间,这里 有可能出现同一时刻 水阀放水的过程,以及放水后 感应到的区域 部分同时感应,所以我们应该联想到 区间合并 ,判断区间是否覆盖完我们的全部管道即可,这里我们 枚举 时间,又因为数据范围较大,枚举时间肯定会 TLE,所以我们又应该联想到二分枚举时间,即可得到最优答案。

? ? ? ? 在这里需要注意的点是,第 L_{i}?? (?T_{i}???S_{i}?) 段到第 L_{i}?+ (?T_{i}???S_{i}?) 段的传感器检测到水流ta它的区间应该为:

L =?L_{i}?? (?T_{i}???S_{i}?) - 1? ? R?=?L_{i}?+ (?T_{i}???S_{i}?)

这里 L 应该为?L_{i}?? (?T_{i}???S_{i}?) - 1 ,是因为我们感应点应该包括 第??L_{i}?? (?T_{i}???S_{i}?) 的点,所以我们区间的左端点 应该 - 1。

区间和并模板代码:


inline void Merge(vector<PII>&p)
{
	int sz = p.size();
	if(sz <= 1) return ; // 如果拥有的区间 <= 1 说明没有合并需要
	
	sort(All(p));	// 先根据端点排序好需要合并的区间
	
	vector<PII>tem;	// 临时存储合并后的区间
	
	PII now = *p.begin();	// 先拿出第一个区间
	
	for(int i = 1;i < sz;++i)
	{
		PII next = p[i];	// 拿出下一个区间,进行比较
		
		if(now.y >= next.y) continue;	// 如果下一个区间被 目前的区间包含,那么合并起来
		
		if(now.y >= next.x) now.y = next.y;	// 如果出现 目前的右端点大于下一个的左端点,合并更新现在的右端点
		else
		{
			tem.emplace_back(now);	// 存储好目前的区间
			now = next;	// 更新目前的区间
		}
	}
	tem.emplace_back(now);	// 存储好最后的区间
	
	p = tem;	// 更新合并好的区间
}

代码详解如下:

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
#define All(x) x.begin(),x.end()
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
using PII = pair<int,int>;

int n,len;

vector<PII>v;// 存储阀门所在点以及开阀时刻


inline void Merge(vector<PII>&p)
{
	int sz = p.size();
	if(sz <= 1) return ; // 如果拥有的区间 <= 1 说明没有合并需要
	
	sort(All(p));	// 先根据端点排序好需要合并的区间
	
	vector<PII>tem;	// 临时存储合并后的区间
	
	PII now = *p.begin();	// 先拿出第一个区间
	
	for(int i = 1;i < sz;++i)
	{
		PII next = p[i];	// 拿出下一个区间,进行比较
		
		if(now.y >= next.y) continue;	// 如果下一个区间被 目前的区间包含,那么合并起来
		
		if(now.y >= next.x) now.y = next.y;	// 如果出现 目前的右端点大于下一个的左端点,合并更新现在的右端点
		else
		{
			tem.emplace_back(now);	// 存储好目前的区间
			now = next;	// 更新目前的区间
		}
	}
	tem.emplace_back(now);	// 存储好最后的区间
	
	p = tem;	// 更新合并好的区间
}

// 二分性质
inline bool cheak(int t)
{
	// 开始获取 t 时刻以内的水流感应到的区间
	vector<PII>edge;
	for(int i = 0;i < n;++i)
	{
		PII now = v[i];
		if(now.y > t)break;
		
		int time = t - now.y;
		
		int l = now.x - time - 1;	// 注意这里的左端点需要 -1
		int r = now.x + time;
		
		edge.emplace_back(PII(l,r));
	}	
	
	// 开始合并区间
	Merge(edge);
	
	if(edge.size() != 1) return false;	// 如果区间不唯一,说明出现未覆盖感应到的管道点。
	else
	{
		PII have = *edge.begin();	// 拿出覆盖的区间,比较是否覆盖感应完了所有管道
		
		if(have.x <= 0 && have.y >= len) return true;
		else return false;
	}
}

inline void solve()
{
	int l = 0,r = -1;	// 二分需要的左右端点,小优化
	v.clear();
	cin >> n >> len;
	for(int i = 0;i < n;++i)
	{
		int L,S;
		cin >> L >> S;
		r = max(S,r);	// 获取最大的开阀时刻
		v.emplace_back(PII(L,S));
	}
	
	// 排序开阀时刻为从小到大
	sort(All(v),[](const PII&a,const PII&b)
	{
		return a.y < b.y;
	});	
	
	r <<= 1;	// 这里 最大时刻开两倍
	
	// 开始 二分 枚举 时间点
	while(l < r)
	{
		int mid = l + r >> 1;
		if(cheak(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << endl;
}

signed main()
{
//	freopen("myout.txt","w+",stdout);
//	freopen("in.txt","r",stdin);
	int _t = 1;
	IOS;
//	cin >> _t;
	while(_t--)
	{
		solve();
	}
	return 0;
}

最后提交:

文章来源:https://blog.csdn.net/hacker_51/article/details/135352138
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。