我的做法是:
用in,out来记录当前最早离开的飞机的离开时刻和所在廊桥
用q来记录目前编号最小的空余廊桥
用vis来记录当前廊桥是否被占用
代码:
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e5 + 10;
int n,m1,m2,x[MAXN],y[MAXN];
bool vis[MAXN];
struct Time{
int s,t;
}a[MAXN],b[MAXN];
struct Node{
int t,id;
bool operator<(const Node &a)const{return this->t > a.t;}
};
bool cmp(Time x,Time y){return x.s < y.s;}
void calc1(){
memset(vis,0,sizeof(vis));
priority_queue<Node> in;
priority_queue<int,vector<int>,greater<int> > q;
for(int i = 1;i <= n;++i){
q.push(i);
vis[i] = 1;
}
for(int i = 1;i <= m1;++i){
while(!in.empty() && a[i].s > in.top().t){
if(!vis[in.top().id]){
q.push(in.top().id);
vis[in.top().id] = 1;
}
in.pop();
}
if(q.size()){
in.push({a[i].t,q.top()});
x[q.top()]++;
vis[q.top()] = 0;
q.pop();
continue;
}
}
for(int i = 1;i <= n;++i) x[i] += x[i - 1];
return ;
}
void calc2(){
memset(vis,0,sizeof(vis));
priority_queue<Node> out;
priority_queue<int,vector<int>,greater<int> > q;
for(int i = 1;i <= n;++i) q.push(i);
for(int i = 1;i <= m2;++i){
while(!out.empty() && b[i].s > out.top().t){
if(!vis[out.top().id]){
q.push(out.top().id);
vis[out.top().id] = 1;
}
out.pop();
}
if(q.size()){
out.push({b[i].t,q.top()});
y[q.top()]++;
vis[q.top()] = 0;
q.pop();
}
}
for(int i = 1;i <= n;++i) y[i] += y[i - 1];
return ;
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m1 >> m2;
for(int i = 1;i <= m1;++i) cin >> a[i].s >> a[i].t;
for(int i = 1;i <= m2;++i) cin >> b[i].s >> b[i].t;
sort(a + 1,a + m1 + 1,cmp);
sort(b + 1,b + m2 + 1,cmp);
calc1();
calc2();
int ans = -1e9;
for(int i = 1;i <= n;++i) ans = max(ans,x[i] + y[n - i]);
cout << ans << endl;
return 0;
}
95分,第一个点WA,其他全对
麻烦大佬们帮忙调一下,万分感谢