当前位置：首页 > news >正文

Acwing2024蓝桥杯区间合并

news 来源：原创 2024/5/22 0:11:39

模板:

#define x first
#define y second
typedef pair<int, int>pii;
pii seg[N];sort(seg,seg+n);
int l=seg[0].x,r=seg[0].y;
for (int i=1;i<n;i++){if (seg[i].x<=r) r=max(r,seg[i].y);else l=seg[i].x,r=seg[i].y;
}

题目:

AcWing 1343. 挤牛奶

#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N=5005;
typedef pair<int,int>pii;
pii seg[N];
int n,ans1,ans2;
int main(){cin>>n;for(int i=0;i<n;i++) cin>>seg[i].x>>seg[i].y;sort(seg,seg+n);int l=seg[0].x,r=seg[0].y;for(int i=0;i<n;i++){if(seg[i].x<=r){r=max(r,seg[i].y);ans1=max(ans1,r-l);}else{ans2=max(ans2,seg[i].x-r);l=seg[i].x,r=seg[i].y;ans1=max(ans1,r-l);}}cout<<ans1<<" "<<ans2<<endl;return 0;
}

AcWing 803. 区间合并

#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N=1e5+5;
typedef pair<int,int>pii;
pii seg[N];
long long ans=1;
int main(){int n;cin>>n;for(int i=0;i<n;i++) cin>>seg[i].x>>seg[i].y;sort(seg,seg+n);int l=seg[0].x,r=seg[0].y;for(int i=0;i<n;i++){if(seg[i].x<=r) r=max(r,seg[i].y);else l=seg[i].x,r=seg[i].y,ans++;}cout<<ans<<endl;return 0;
}

AcWing 422. 校门外的树

#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N=105;
typedef pair<int,int>pii;
pii seg[N];
int ans;
int main(){int len,n;cin>>len>>n;for(int i=0;i<n;i++) cin>>seg[i].x>>seg[i].y;sort(seg,seg+n);int l=seg[0].x,r=seg[0].y;for(int i=0;i<n;i++){if(seg[i].x<=r) r=max(r,seg[i].y);else ans+=r-l+1,l=seg[i].x,r=seg[i].y;}ans+=r-l+1;cout<<len+1-ans<<endl;return 0;
}

AcWing 5407. 管道(第十四届省赛)

#include<iostream>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N=1e5+5;
int n,len,id[N],timee[N];
typedef pair<int,int>pii;
pii seg[N];
bool check(long long value){int j=0,flag=1;//划分区间for(int i=1;i<=n;i++){if(timee[i]<=value){//flag进行标记flag=0;int temp=value-timee[i];seg[j].x=max(1,id[i]-temp),seg[j].y=min(len,id[i]+temp),j++;}}//如果flag==1则该时间绝对不可能if(flag) return false;//排序sort(seg,seg+j);//合并区间int l=seg[0].x,r=seg[0].y,cnt=0;for(int i=0;i<j;i++){if(seg[i].x<=r+1) r=max(r,seg[i].y);else{//cnt计数cnt+=r-l+1;l=seg[i].x;r=seg[i].y;}//最后一次合并区间后,cnt计数if(i==j-1) cnt+=r-l+1;}//check判断boolif(cnt==len) return true;else return false;
}
int main(){//输入cin>>n>>len;for(int i=1;i<=n;i++) cin>>id[i]>>timee[i];//二分查找int left=1,right=2e9;//注意right的值为2e9while(left<right){//注意mid开浪浪,否则最大测试数据会爆long long mid=(long long)left+right>>1;if(check(mid)) right=mid;else left=mid+1;}//输出cout<<left<<endl;return 0;
}