CSP-S 2021 T1廊桥分配

CSP-S 2021 T1廊桥分配

枚举分配给国内航班和国外航班的廊桥数量，若分配给国内机场$i$个廊桥，则国外机场就有$n-i$个廊桥，在此基础上分别判断两边各能通过多少飞机。用一个小根堆存储飞机离开的时间，枚举到一个飞机到达的时间时，将小根堆中的这个到达时间之前的点弹出，复杂度$O(n(m1+m2))$，可以通过$n\le 5000,m_1+m_2\le 5000$的数据，拿到$40$分（实际$45$分）。

#include <bits/stdc++.h>
#define A 100010using namespace std;
struct node {int a, b;friend bool operator < (const node x, const node y) {if (x.a != y.a) return x.a < y.a;else return x.b < y.b;}
}e1[A], e2[A];
int n, m1, m2, ans;int main(int argc, char const *argv[]) {cin >> n >> m1 >> m2;for (int i = 1; i <= m1; i++) {scanf("%d%d", &e1[i].a, &e1[i].b);}for (int i = 1; i <= m2; i++) {scanf("%d%d", &e2[i].a, &e2[i].b);}sort(e1 + 1, e1 + m1 + 1);sort(e2 + 1, e2 + m2 + 1);priority_queue<int, vector<int>, greater<int> > q;for (int i = 0; i <= n; i++) {int ti = i, tj = n - i;int sum1 = 0, sum2 = 0;if (ti == 0) {sum1 = 0;}else {while (q.size()) q.pop();for (int j = 1; j <= m1; j++) {while (!q.empty() and e1[j].a >= q.top()) q.pop(), ti++;if (ti - 1 >= 0) {sum1++;q.push(e1[j].b);ti--;}}}if (tj == 0) {sum2 = 0;}else {while (q.size()) q.pop();for (int j = 1; j <= m2; j++) {while (!q.empty() and e2[j].a >= q.top()) q.pop(), tj++;if (tj - 1 >= 0) {sum2++;q.push(e2[j].b);tj--;}}}ans = max(ans, sum1 + sum2);}cout << ans << endl;
}

假设已经有$n$架飞机通过$m$个廊桥完成了降落，如果此时来了第$n+1$架飞机，那么这架飞机不会影响之前$n$架飞机的降落情况（具体降落在哪个廊桥）。所以我们可以模拟出每架飞机降落时所抵达的廊桥编号，同时也就知道了每个廊桥降落过飞机的数量。
例如编号为$1$的廊桥降落过$3$架飞机，编号为$2$的廊桥降落过$3$架飞机，编号为$3$的廊桥降落过$2$架飞机，在这种情况下如果有$2$个廊桥，那么可以停留的飞机数量就是$3+3=6$；如果有$3$个廊桥，可以停留的飞机数量就是$3+3+2=8$。

具体实现时，使用一个优先队列$q$表示某家飞机的到达时间和离开时间，与部分分做法表示的含义相同，但还需要加一个所停靠廊桥的编号，因此可以使用pair<int,int>来存储。另一个优先队列$qq$表示空闲的廊桥编号，初始时$n$个廊桥都空闲，所以将$n$个廊桥都加入优先队列$qq$。

#include <bits/stdc++.h>
#define A 100010
#define pi pair<int, int>using namespace std;
struct node {int a, b;friend bool operator < (const node x, const node y) {if (x.a != y.a) return x.a < y.a;else return x.b < y.b;}
}e1[A], e2[A];
int n, m1, m2, ans, f1[A], f2[A];int main(int argc, char const *argv[]) {cin >> n >> m1 >> m2;for (int i = 1; i <= m1; i++) {scanf("%d%d", &e1[i].a, &e1[i].b);}for (int i = 1; i <= m2; i++) {scanf("%d%d", &e2[i].a, &e2[i].b);}sort(e1 + 1, e1 + m1 + 1);sort(e2 + 1, e2 + m2 + 1);priority_queue<pi, vector<pi>, greater<pi> > q;priority_queue<int, vector<int>, greater<int> > qq;for (int i = 1; i <= n; i++) qq.push(i);for (int i = 1; i <= m1; i++) {while (!q.empty() and e1[i].a >= q.top().first) {qq.push(q.top().second);q.pop();}if (qq.empty()) continue;int top = qq.top();qq.pop();f1[top]++;q.push(make_pair(e1[i].b, top));}for (int i = 1; i <= n; i++) f1[i] += f1[i - 1];while (!q.empty()) q.pop();while (!qq.empty()) qq.pop();for (int i = 1; i <= n; i++) qq.push(i);for (int i = 1; i <= m2; i++) {while (!q.empty() and e2[i].a >= q.top().first) {qq.push(q.top().second);q.pop();}if (qq.empty()) continue;int top = qq.top();qq.pop();f2[top]++;q.push(make_pair(e2[i].b, top));}for (int i = 1; i <= n; i++) f2[i] += f2[i - 1];for (int i = 0; i <= n; i++)ans = max(ans, f1[i] + f2[n - i]);cout << ans << endl;
}