按第一个题解的思路自己写的,第19个点和补的3个点超时了
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+5;
int n,m1,m2,ans;
struct node{
int x,y;//抵达时间 离开时间
};
node d1[N],d2[N];
bool cmp(node a,node b){
return a.x<b.x;//先到先得
}
struct lq{
int f,n;//廊桥状态 累计数量
};
lq a[N],b[N];
struct tk{
int lq,y;//廊桥编号 离开时间
};
struct tkcmp{
bool operator()(const tk& a,const tk& b){
return a.y>b.y;
}
};
int main(){
scanf("%d%d%d",&n,&m1,&m2);//获取廊桥总数和国内区航班数和国际区航班数
for(int i=1;i<=m1;i++) scanf("%d%d",&d1[i].x,&d1[i].y);//获取国内区航班抵达离开时间
for(int i=1;i<=m2;i++) scanf("%d%d",&d2[i].x,&d2[i].y);//同上
sort(d1+1,d1+1+m1,cmp);//按抵达时间排序
sort(d2+1,d2+1+m2,cmp);
//假设廊桥数量无限多 到达的飞机占用编号最小的空闲廊桥 并统计每个廊桥停过多少航班
//那么廊桥1~n能停的航班总数就是n个廊桥能停的总数
//按离开时间升序排列停机情况
priority_queue<tk,vector<tk>,tkcmp> q1,q2;
for(int i=1;i<=m1;i++){//遍历国内区航班 记录每个廊桥能停靠多少个航班
if(q1.empty()){
q1.push({1,d1[i].y});//进入停靠队列
a[1].f=1;//廊桥状态变为繁忙
a[1].n++;//分配廊桥 对应廊桥累计停靠数量增加
}else{
while(!q1.empty()&&d1[i].x>q1.top().y){//将飞机离开的廊桥变为空闲
a[q1.top().lq].f=0;
q1.pop();
}
for(int j=1;j<=m1;j++) if(a[j].f==0){
a[j].f=1;
q1.push({j,d1[i].y});
a[j].n++;
break;
}
}
}
for(int i=1;i<=m2;i++){//遍历国际区航班
if(q2.empty()){
q2.push({1,d2[i].y});//进入停靠队列
b[1].f=1;//廊桥状态变为繁忙
b[1].n++;//分配廊桥 对应廊桥累计停靠数量增加
}else{
while(!q2.empty()&&d2[i].x>q2.top().y){
b[q2.top().lq].f=0;
q2.pop();
}
for(int j=1;j<=m2;j++) if(b[j].f==0){
b[j].f=1;
q2.push({j,d2[i].y});
b[j].n++;
break;
}
}
}
for(int i=1;i<=n;i++){//每个廊桥可停靠航班数做成前缀和 即是对应数量廊桥可停靠航班数
a[i].n+=a[i-1].n;
b[i].n+=b[i-1].n;
}
for(int i=0;i<=n;i++) ans=max(ans,a[i].n+b[n-i].n);
printf("%d",ans);
return 0;
}