CSP-S T1求助
查看原帖
CSP-S T1求助
332549
幽灵特工楼主2021/10/27 19:18

思路是先用优先队列分别求出给国内或国外分配0~n个廊桥时可以停靠的飞机数量,然后O(n)找到最大值。但是写挂了(本人已AFO一月,代码能力--)

第一个样例都过不了,

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
int n,m1,m2;
int ans1[MAXN],ans2[MAXN];
struct p{
	int l,r;
	p(int x,int y){
		l=x;r=y;
	}
	bool operator < (p a)const {
		return this->l>a.l;
	}
};
priority_queue <p> q;
priority_queue <int,vector<int>,greater<int> > ri;
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m1>>m2;
	int x,y;
	for(int i=0;i<m1;i++){
		cin>>x>>y;
		q.push(p(x,y));
	}
	int t=0;
	while(!q.empty()){
		p a=q.top();q.pop();
		ri.push(a.r);
		t++;
		while(a.l>=ri.top()){
			t--;
			ri.pop();
		}
		ans1[t]++;
	}
	while(!ri.empty())ri.pop();
	for(int i=2;i<=n;i++)ans1[i]+=ans1[i-1];
	for(int i=0;i<m2;i++){
		cin>>x>>y;
		q.push(p(x,y));
	}
	t=0;
	while(!q.empty()){
		p a=q.top();q.pop();
		ri.push(a.r);
		t++;
		while(a.l>=ri.top()){
			t--;
			ri.pop();
		}
		ans2[t]++;
	}
	for(int i=2;i<=n;i++)ans2[i]+=ans2[i-1];
	int maxn=0;
	for(int i=0;i<=n;i++){
		maxn=max(maxn,ans1[i]+ans2[n-i]);
	}
	cout<<maxn;
}
2021/10/27 19:18
加载中...