【区间合并专题】【蓝桥杯备考训练】：挤牛奶、区间合并、校门外的树、管道【已更新完成】

目录

1、挤牛奶（usaco training 1.3）

2、区间合并（模板）

3、校门外的树（NOIP2005普及组）

4、管道（第十四届蓝桥杯 省赛 python B组）

1、挤牛奶（usaco training 1.3）

每天早上 5 点，三名农夫去牛场给奶牛们挤奶。

现在从 5 点开始按秒计时，第一名农夫在第 300秒开始给牛挤奶，并在第 1000 秒停止挤奶。

第二名农夫在第 700 秒开始给牛挤奶，并在第 1200 秒停止挤奶。

第三名农夫在第 1500 秒开始给牛挤奶，并在第 2100 秒停止挤奶。

从开始挤奶到挤奶完全结束，这一期间，至少存在一名农夫正在挤奶的连续时间段的长度最长为 900 秒（第 300 秒至第 1200 秒），完全没有任何农夫在挤奶的连续时间段的长度最长为 300 秒（第 1200 秒至第 1500 秒）。

现在给你 N 名农夫挤 N 头奶牛的工作时间表，请你求出：

1. 至少存在一名农夫正在挤奶的连续时间段的最长长度。
2. 没有任何农夫在挤奶的连续时间段的最长长度。

注意：本题中给出的所有时间均为时刻（时间点），因此在本题中挤奶区间 [100，200]和 [201,300] 中间会有长度为 1 秒的间歇时间。

输入格式

第一行包含整数 N，表示农夫数量。

接下来 N 行，每行包含两个非负整数 l,r表示农夫挤奶的开始时刻和结束时刻。

输出格式

共一行，包含两个整数，分别表示最长连续挤奶时间以及最长连续无人挤奶时间。

数据范围

1≤N≤5000
0≤l≤r≤106

输入样例：

3
300 1000
700 1200
1500 2100

输出样例：

900 300

代码：

一个简单的区间合并，用两个变量分别维护最长区间、最长区间空隙即可

思路：

//变量维护最长的区间和最长的断开区间即可
#include<bits/stdc++.h>

using namespace std;

int n;

const int N=5000+5;

typedef long long LL;

typedef pair<int,int> PII;

#define x first

#define y second

vector<PII>nums,res;

int main()
{
	cin>>n;
	
	for(int i=1;i<=n;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		nums.push_back({l,r});
	}
	
	int st=-2e9,ed=-2e9;
	sort(nums.begin(),nums.end());
	int maxs=nums[0].y-nums[0].x,mins=0;
	for(auto num :nums)
	{
		//无法合并 
		if(ed<num.x)
		{
			if(ed!=-2e9)mins=max(mins,num.x-ed);
			st=num.x;
			ed=num.y;
			res.push_back(num);
		}
		else if(ed<num.y)
		{
			ed=num.y;
			maxs=max(maxs,ed-st);
		}
	}
	maxs=max(maxs,res.back().y-res.back().x);
	cout<<maxs<<" "<<mins;
	return 0;
}

2、区间合并（模板）

给定 n 个区间 [li,ri]要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3]和 [2,6]可以合并为一个区间 [1,6]。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围

1≤n≤100000
−109≤li≤ri≤109

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

思路：

经典的区间合并（比上一题少两个需要维护的变量），且看代码

代码：

#include<bits/stdc++.h>

using namespace std;

#define x first

#define y second

typedef pair<int,int> PII;

int n;

vector<PII> a,res;

int main()
{
	cin>>n;
	
	for(int i=0;i<n;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		
		PII t={l,r};
		 
		a.push_back(t);
	}
	
	int st=-2e9,ed=-2e9;
	sort(a.begin(),a.end());
	for(auto num:a)
	{
		//无法合并 
		if(num.x>ed)
		{
			ed=num.y;
			res.push_back(num);
		}
		else if(ed<num.y)
		{
			ed=num.y;
		}
	}
	cout<<res.size();
	return 0;
} 

3、校门外的树（NOIP2005普及组）

某校大门外长度为 L 的马路上有一排树，每两棵相邻的树之间的间隔都是 1米。

我们可以把马路看成一个数轴，马路的一端在数轴 0 的位置，另一端在 L 的位置；数轴上的每个整数点，即 0，1，2，……，L都种有一棵树。

由于马路上有一些区域要用来建地铁。

这些区域用它们在数轴上的起始点和终止点表示。

已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。

现在要把这些区域中的树（包括区域端点处的两棵树）移走。

你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入格式

输入文件的第一行有两个整数 L 和 M，L 代表马路的长度，M代表区域的数目，L 和 M 之间用一个空格隔开。

接下来的 M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出格式

输出文件包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

数据范围

1≤L≤10000
1≤M≤100

输入样例：

500 3
150 300
100 200
470 471

输出样例：

298

思路：

统计区间总和，再用L再减去即可，注意两端都有树，所以都要+1

代码：

#include<bits/stdc++.h>

using namespace std;

int l,n;

#define x first

#define y second

const int L=1e4+5;

typedef long long LL;

typedef pair<int,int> PII;

int st=-2e9,ed=-2e9;

vector<PII>nums,res;

int main()
{
	cin>>l>>n;
	
	for(int i=1;i<=n;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		
		nums.push_back({l,r});
		
	}
	
	sort(nums.begin(),nums.end());
	int sum=0;
	for(auto num:nums)
	{
		if(num.x>ed)
		{
		    if(ed!=-2e9)sum+=ed-st+1;//端点的也算上
			ed=num.y;
			st=num.x;
			res.push_back(num);
		}
		else if(ed<num.y)
		{
			ed=num.y;
		}
	}
	
	sum+=ed-st+1;//端点的也算上
	
	cout<<l+1-sum;//本来有l+1棵树
	return 0;
} 

4、管道（第十四届蓝桥杯 省赛 python B组）

4、管道（第十四届蓝桥杯 省赛 python B组）
有一根长度为 len 的横向的管道，该管道按照单位长度分为 len 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。

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

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

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

输入格式

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

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

输出格式

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

数据范围

对于 30% 的评测用例，n≤200，Si,len≤3000；
对于 70% 的评测用例，n≤5000，Si,len≤1e5；
对于所有评测用例，1≤n<=1e5，1≤Si,len≤1e9;

输入样例：

3 10
1 1
6 5
10 2

输出样例：

5

思路：

二分+区间和并

题目意思是每个开关会往两边放水（这就可以考虑到区间和并），看最早哪个时刻所有水管可以注满

先对每一个时刻进行分析，看是否能注满水，因为某一个时刻如果能注满水，那这个时刻之后都能注满水，具有单调性（这也是可以二分的原因），因此我们考虑二分搜索，我们可以二分出最早注满水的时刻

需要注意的是区间合并的时候条件需要修改一下，ed+1小于等于第二个区间的时候就可以合并了（因为管道不需要端点重合）

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10; 

typedef long long LL;

typedef pair<int,int> PII;

PII w[N],q[N];

int n,len;

bool check(int mid)//判断某一个时刻是否能注满 
{
	int cnt=0;//打开阀门的数量 
	for(int i=0;i<n;i++)
	{ 
		int pos=w[i].first;
		if(mid<w[i].second)
		{
			continue;//比该阀门打开时间晚，那就不计入
		}
		else
		{
			int d=mid-w[i].second;//经过的距离
			q[cnt].first=max(1,pos-d);
			q[cnt].second=min((LL)pos+d,(LL)len); 
			cnt++;
		}
	}
	//区间合并
	sort(q,q+cnt);
	
	int st=-2e9,ed=-2e9;
	
	for(int i=0;i<cnt;i++)
	{
		if(ed+1<q[i].first)//不能合并的情况 
		{
			st=q[i].first;
			ed=q[i].second;		
		}
		else ed=max(ed,q[i].second);	
	}
	//cout<<cnt<<endl;
	return st==1 && ed==len;
}

int main()
{
	cin>>n>>len;
	
	for(int i=0;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		w[i]={a,b};
	}
	
	int l=1,r=2e9;//最晚会在2e9覆盖 
	
	while(l<r)
	{
		int mid=(LL)l+r>>1;//用l=mid+1的模板
		if(check(mid))r=mid;
		else l=mid+1; 
	}
	
	cout<<l<<endl;
	
	return 0;
}