噢莫加纳加加加 • 2个月前
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n;
struct range { //结构体存航班到达时间和离开时间
int x, y;
} a[100005], b[100005]; //国内航班和国际航班
typedef pair<int, int>pii; //定义一个类型,表示一个整数对
int res1[100005], res2[100005];//结果
bool cmp(const range &a, const range &b) {
return a.x < b.x ;
}
void calc(range *t, int m, int *res) {
priority_queue<pii, vector<pii>, greater<pii> > lq;
priority_queue<int, vector<int>, greater<int> > wq;
for (int i = 1; i <= n; i++) {
wq.push(i);
}
for (int i = 1; i <= m; i++) {
while (!lq.empty() && t[i].x >= lq.top().first) {
wq.push(lq.top().second);
lq.pop();
}
if (wq.empty())
continue;
int dest = wq.top();
wq.pop();
res[dest]++;//桶排
lq.push(make_pair(t[i].y, dest));
}
for (int i = 1; i <= n; i++) {
res[i] += res[i - 1];
}
}
int main() {
int m1, m2;
cin >> n >> m1 >> m2;
//读入航班到达时间、离开时间
for (int i = 1; i <= m1; i++) {
cin >> a[i].x >> a[i].y;
}
for (int i = 1; i <= m2; i++) {
cin >> b[i].x >> b[i].y;
}
//对国内航班和国际航班进行排序
sort(a + 1, a + m1 + 1, cmp);
sort(b + 1, b + m2 + 1, cmp);
//计算两个航班列表的结果
calc(a, m1, res1);
calc(b, m2, res2);
//计算最大空闲廊桥数量
int ans = 0;
for (int i = 0; i <= n; i++) {
ans = max(ans, res1[i] + res2[n - i]);
}
cout << ans << endl;
return 0;
}
评论:
请先登录,才能进行评论