思路是先用优先队列分别求出给国内或国外分配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;
}