2021 CSP 题解
T1 廊桥分配
这是一道非常有趣的题目,反正当时一眼看去就是个三分,然后样例全过,$fst$ 了不少。
因为国内航班飞机和国际航班飞机 不能停靠在 同一个区。
这就导致了状态 可能性变数过大,从而增加了枚举的难度,
如果是按照朴素方法枚举,复杂度会达到 $O(n^2logn)$,太大了,那该怎么办呢?
由于这道题不满足 凸函数 性质,所以不能用二分、三分来优化时间复杂度。
在这种情况下,一般的,能想到如果 不能直接找到 要怎么分配,可不可以先预处理,再一一判断。
显然的,如果 分别预处理 两种飞机的停靠,是满足 单调性质 的,那么,就可以做一些其它的考量。
想要快速处理将飞机停靠在 不同数量的廊桥上 所容纳的飞机,就不要去重复处理同一件事。
这一点,可以用 前缀和 解决。
那我们就需要一个能够在 $log n$ 的时间内查找飞机 最晚离开时间 的算法。
这样的算法往往有两种选择 优先队列 或 平衡树。
但是,这不仅仅是要查找 最晚离开时间,还要具有删除功能。
这需要用到 懒惰删除法,这里是直接用 set 解决。
#include <bits/stdc++.h>
#define x first
#define y second
#define For(i, j, k) for (int i = j; i <= k; i ++ )
using namespace std;
const int N = 100010, INF = N;
typedef pair<int, int> PII;
int ans;
int n, m1, m2;
PII a[N];
PII b[N];
set<PII> A, B;
set<PII>::iterator id;
int num1[N], num2[N];
int add(set<PII> &S)
{
int res = 0, now = 0;
For(i,0,INF)
{
id = S.lower_bound({now, now}); // 寻找进入机场的飞机中最早的一个, 返回它所在的迭代器
if (id == S.end()) break; // 退出
res ++, now = (*id).y;
S.erase(id);
}
return res;
}
int main()
{
scanf("%d %d %d", &n, &m1, &m2);
For(i, 1, m1) scanf("%d %d", &a[i].x, &a[i].y);
For(i, 1, m2) scanf("%d %d", &b[i].x, &b[i].y);
For(i, 1, m1) A.insert(a[i]);
For(i, 1, m2) B.insert(b[i]);
For(i, 1, n) num1[i] = num1[i - 1] + add(A);
For(i, 1, n) num2[i] = num2[i - 1] + add(B);
For(i, 0, n) ans = max(ans, num1[i] + num2[n - i]);
printf("%d", ans);
return 0;
}