1 solutions
-
0
#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,int> PII; const int N=100010; int n,m1,m2; PII q1[N],q2[N]; int s1[N],s2[N]; void calc(int m,PII q[],int s[]) { sort(q,q+m); //按照到达的先后顺序从小到达排序 priority_queue<int,vector<int>,greater<int>> idle; //空闲的廊桥(按照廊桥的编号从小到达排序) priority_queue<PII,vector<PII>,greater<PII>> full; //已经占用的廊桥(按照飞机离开的时间从小到大排序) for(int i=1;i<=n;i++) idle.push(i); for(int i=0;i<m;i++) //枚举每个飞机 { int st=q[i].x,ed=q[i].y; //获取到达时间和离开时间 while(full.size()&&full.top().x<st) //弹出这个飞机后面相对空闲的廊桥 { idle.push(full.top().y); //这个廊桥是空闲的了 full.pop(); //弹出廊桥 } if(idle.empty()) continue; //这个飞机找不到廊桥 int t=idle.top(); //找到编号最小的空闲的廊桥 idle.pop(); //弹出空闲 s[t]++; //数量增加 full.push({ed,t}); //增加一个占用的廊桥 } for(int i=1;i<=n;i++) //预处理前缀和 { s[i]+=s[i-1]; } } int main() { cin>>n>>m1>>m2; for(int i=0;i<m1;i++) { cin>>q1[i].x>>q1[i].y; } for(int i=0;i<m2;i++) { cin>>q2[i].x>>q2[i].y; } calc(m1,q1,s1); //国内航班的模拟 calc(m2,q2,s2); //国外航班的模拟 int res=0; for(int i=0;i<=n;i++) //枚举廊桥的分类 { res=max(res,s1[i]+s2[n-i]); } cout<<res; return 0; }
Information
- ID
- 1146
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 10
- Tags
- # Submissions
- 9
- Accepted
- 2
- Uploaded By