求各位大佬指教一下
查看原帖
求各位大佬指教一下
232796
Deson楼主2022/8/22 00:32
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct nds{
	int s,t;
}a[maxn],b[maxn];
bool cmp(nds x,nds y){
	return x.s<y.s;
}
typedef pair<int,int> Pair; 
int dp1[maxn],dp2[maxn];
int pre[maxn]; 
int main(){
// 	freopen("airport,in", "r", stdin);
//     freopen("airport.out", "w", stdout);
	int n,m1,m2;
	cin >> n >> m1 >> m2;
	for(int i=1;i<=m1;i++){
		cin >> a[i].s >> a[i].t;
	}
	sort(a+1,a+m1+1,cmp);
	for(int i=1;i<=m2;i++){
		cin >> b[i].s >> b[i].t;
	}
	sort(b+1,b+m2+1,cmp);
	priority_queue<Pair,vector<Pair>,greater<Pair> >q;
	priority_queue<int,vector<int>,greater<int> >q1;
	for(int i=1;i<=m1;i++){
		if(q.empty()){
			q.push(make_pair(a[i].t,1));
			dp1[1]++;
		}
		else if(q.top().first<=a[i].s) {
			while(q.top().first<=a[i].s){
				q1.push(q.top().second);
				q.pop();
			} 
			int x = q1.top();
			q1.pop();
			q.push(make_pair(a[i].t,x));
			dp1[x]++;
		}
		else{
			q.push(make_pair(a[i].t,q.size()+1));
			dp1[q.size()]++;
		}
	}
	while(!q.empty()){
		q.pop();
	}
	while(!q1.empty()){
		q1.pop();
	}
	for(int i=1;i<=m2;i++){
		if(q.empty()){
			q.push(make_pair(b[i].t,1));
			dp2[1]++;
		}
		else if(q.top().first<=b[i].s) {
			while(q.top().first	<=b[i].s){
				q1.push(q.top().second);
				q.pop();
			} 
			int x = q1.top();
			q1.pop();
			q.push(make_pair(b[i].t,x));
			dp2[x]++;
		}
		else{
			int len = q.size();
			q.push(make_pair(b[i].t,len+1));
			dp2[len+1]++;
		}
	}
	for(int i=1;i<=n;i++){
		dp1[i] += dp1[i-1];
		dp2[i] += dp2[i-1];
	}
	int ans = -1;
	for(int i=0;i<=n;i++){
		ans = max(ans,dp1[i]+dp2[n-i]);
	}
	cout << ans;
	return 0;
} 

2022/8/22 00:32
加载中...