CE求助
查看原帖
CE求助
490978
小超手123楼主2022/8/30 12:14
#include<bits/stdc++.h>
using namespace std;
int n,m1,m2,sum1[100005],sum2[100005];  //sum[i]表示分配i座廊桥的价值
int ans=0;
struct node {
	int l,r,v;
	friend bool operator < (node x,node y) {
		return x.r>y.r;
	}
};
node a[100005],b[100005];
bool cmp(node x,node y) {
	return x.l<y.l;
}
void solve1() {
	priority_queue<node,vector<node>,greater<node> >Air; //维护等待离港航班
	priority_queue<int,vector<int>,greater<int> >LQ; //维护空闲的廊桥编号
	for(int i=1; i<=n; i++) LQ.push(i);
	for(int i=1; i<=m1; i++) {
		while(!Air.empty()&&a[i].l>=Air.top().r) {
			LQ.push(Air.top().v);
			Air.pop();
		}
		if(LQ.empty())continue;
		sum1[LQ.top()]++;
		Air.push((node){a[i].l,a[i].r,LQ.top()});
		LQ.pop();
	}
	for(int i=1; i<=n; i++)sum1[i]+=sum1[i-1];
}

void solve2() {
	priority_queue<node,vector<node>,greater<node> >Air; //维护等待离港航班
	priority_queue<int,vector<int>,greater<int> >LQ; //维护空闲的廊桥编号
	for(int i=1; i<=n; i++) LQ.push(i);
	for(int i=1; i<=m2; i++) {
		while(!Air.empty()&&b[i].l>=Air.top().r) {
			LQ.push(Air.top().v);
			Air.pop();
		}
		if(LQ.empty())continue;
		sum2[LQ.top()]++;
		Air.push((node) {
			b[i].l,b[i].r,LQ.top()
		});
		LQ.pop();
	}
	for(int i=1; i<=n; i++)sum2[i]+=sum2[i-1];
}
int main() {
	cin>>n>>m1>>m2;
	for(int i=1; i<=m1; i++)
	    cin>>a[i].l>>a[i].r;
	for(int i=1; i<=m2; i++)
	    cin>>b[i].l>>b[i].r;
	sort(a+1,a+m1+1,cmp);
	sort(b+1,b+m2+1,cmp);
	solve1();
	solve2();
	for(int i=1; i<=n; i++)
	    if(sum1[i]+sum2[n-i]>ans)ans=sum1[i]+sum2[n-i];
	cout<<ans;
	return 0;
}
2022/8/30 12:14
加载中...