【区间合并专题】【蓝桥杯备考训练】:挤牛奶、区间合并、校门外的树、管道【已更新完成】
目录
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 头奶牛的工作时间表,请你求出:
- 至少存在一名农夫正在挤奶的连续时间段的最长长度。
- 没有任何农夫在挤奶的连续时间段的最长长度。
注意:本题中给出的所有时间均为时刻(时间点),因此在本题中挤奶区间 [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;
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/271536.html 如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!