专栏文章

8-8作业/重写ren_gao_zu

个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioful4m
此快照首次捕获于
2025/12/02 18:31
3 个月前
此快照最后确认于
2025/12/02 18:31
3 个月前
查看原文

作业

D4219 区间合并

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5;
struct node{
	int l,r;
}a[N];
bool cmp(node x,node y){
	if(x.l==y.l){
		return x.r>y.r;
	}return x.l<y.l;
}
int n,ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
	}sort(a+1,a+n+1,cmp);
	int r1=a[1].r,l1=a[1].l;
	for(int i=2;i<=n;i++){
		if(a[i].l<=r1)r1=max(a[i].r,r1);
		else{
			printf("no");
			return 0;
		}
	}printf("%d %d",l1,r1);
	return 0;
}

P2434 [SDOI2005] 区间

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
struct node{
	int l,r;
}a[N];
bool cmp(node x,node y){
	if(x.l==y.l)return x.r>y.r;
	return x.l<y.l;
}
int n,ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;
	sort(a+1,a+n+1,cmp);
	int l1=a[1].l,r1=a[1].r;
	for(int i=2;i<=n;i++){
		if(a[i].l<=r1)r1=max(a[i].r,r1);
		else{
			cout<<l1<<" "<<r1<<endl;
			l1=a[i].l,r1=a[i].r;
		}
	}cout<<l1<<" "<<r1;
	return 0;
}

重写

P1496 火烧赤壁

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5;
struct node{
	int l,r;
}a[N];
bool cmp(node x,node y){
	return x.l<y.l;
}
int n,ans;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;
	sort(a+1,a+n+1,cmp);
	int l1=a[1].l,r1=a[1].r;
	for(int i=2;i<=n;i++){
		if(r1<=a[i].l){
			ans+=r1-l1;
			l1=a[i].l;
			r1=a[i].r;
		}
		else{
			r1=max(a[i].r,r1);
		}
	}cout<<ans+r1-l1;
	return 0;
}

P1668 [USACO04DEC] Cleaning Shifts S

CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int t,n;
struct node{
	int l,r;
}a[N];
int ans=1;
bool cmp(node x,node y){
	if(x.l==y.l)return x.r>y.r;
	return x.l<y.l;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>t;
	for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r;
	sort(a+1,a+n+1,cmp);
	if(a[1].l>1){
		cout<<-1;
		return 0;
	}
	int la=a[1].r+1;
	
	for(int i=2;i<=n;i++){
		if(a[i].l>la){
			cout<<-1;
			return 0;
		}
		if(a[i].r<la)continue;
		else{
			int id,ma=0;
			for(int j=i;j<=n;j++){
				if(a[j].l>la)break;
				else{
					if(ma<a[j].r){
						ma=a[j].r;
						id=j;
					}
				}
			}
			if(ma>=t){
				cout<<ans+1;
				return 0;
			}
			la=a[id].r+1,ans++;
		}
		
	}
	if(la<=t)cout<<-1;
	else cout<<ans;
	return 0;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...