当前位置: 首页 > article >正文

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

目录

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;
}
原文地址:https://blog.csdn.net/2301_76941161/article/details/136668895
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/271536.html

相关文章:

  • HashMap和HashTable的区别
  • 车载GNSS —— 支撑城市NOA落地的关键技术
  • FDM3D打印系列——水补土和喷漆
  • Flutter 当涉及Listview的复杂滑动布局良好布局方式
  • 突破编程_C++_C++11新特性(function与bind绑定器)
  • 2.26回顾章节主体线索脉络,课程要求(评分)
  • C++ time
  • 指针基础 - golang版
  • 蓝桥杯刷题|01普及-真题
  • Qt 实现 Asterix 报文解析库
  • 【Sql Server】通过Sql语句批量处理数据,使用变量且遍历数据进行逻辑处理
  • ArcGIS分享图层数据的最佳方法
  • Jupyter Notebook出错提示An error occurred while retrieving package information解决办法
  • 我是继续学习编程,还是学数控?
  • Linux查看mysql安装目录
  • 刷题记录[导航贴]
  • C++算法学习心得八.动态规划算法(4)
  • C#常见的.Net类型(二)
  • c语言:汽车时代
  • go get x509:certificate signed by unknown authority