45pts 求调
查看原帖
45pts 求调
941743
zhujianheng楼主2023/9/24 13:42
#include<bits/stdc++.h>
using namespace std;
struct code{
	int g,q;
};
typedef pair<int,int> PII;
code a[200010];
code b[200010];
vector<int> plane1(200010,0),plane2(200010,0);
int n;
int cmp(code a,code b){
	return a.g<b.g;
}
void js(code *a,int &len,vector<int> &plane){
	priority_queue<PII,vector<PII>,greater<PII> > a1;
	priority_queue<int,vector<int>,greater<int> > b1;
	for(int i=1;i<=n;i++) b1.push(i);
	for(int i=1;i<=len;i++){
		if(!a1.empty() && a[i].g>=a1.top().first){//如果当前航班的抵达时间早于之前某个航班 
			b1.push(a1.top().second);//就把某个廊桥分配给这个航班 
			a1.pop();//这个航班飞走了 
		}
		if(b1.empty()) continue;//如果当前没有一个航班被分配到廊桥,那么继续寻找下一个 
		int now=b1.top();//当前最早的航班
		b1.pop();
		plane[now]++;//这个航班之前占用廊桥的航班数量增加1
		a1.push(make_pair(a[i].q,now));//把这个航班放入等待离岸航班 
	}
	for(int i=1;i<=n;i++) plane[i]+=plane[i-1];//当前所有的用廊桥的航班的总和,就是最后的结果 
}
int main(){
	int m1,m2;
	int cnt=0;
	int max1=0;
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++) cin>>a[i].g>>a[i].q;
	for(int i=1;i<=m2;i++) cin>>b[i].g>>b[i].q;
	sort(a+1,a+m1+1,cmp);
	sort(b+1,b+m2+1,cmp);
	js(a,m1,plane1);
	js(b,m2,plane2);
	int ans=0;
	for(int i=0;i<=n;i++)
		ans=max(ans,plane1[i]+plane2[n-i]);
	cout<<ans<<endl;
	return 0;
}
2023/9/24 13:42
加载中...