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 100010

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;

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;
}

原文地址：https://blog.csdn.net/yandaoqiusheng/article/details/142675714

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！