前言

如果您是从 ljt 的 CSP 游记过来的，那么您应该已经知道了 CE 惨案。如果您和我一样有这一类问题的话可以访问这个帖子，上面有一些值得采纳的建议。

题解

设 $s1_i$ 为国内航班有 $i$ 个停机位时能停在停机位的新增加的飞机个数。$s2_i$ 为国际，同理。

那么，我们需要一个结构体的优先队列来存每一个停机位的信息：会被占用到多久，停机位的编号。按照被占用截止时间从小到大排序。

而且，优先队列里只能存此时被占用的停机位。

具体实现

国内和国际分开枚举。

拿一个 bool 数组 $is\_zhan$，$is\_zhan_i$ 代表第 $i$ 个停机位是否被占用。

每一次有一个飞机来的时候，就先把所被有占用截止时间小于这个飞机到达时间的停机位全部弹掉，然后从 $1$ 号机位开始统计，直到枚举到一个没有被占用的机位 $j$，就意味着这个飞机在机位数量至少为 $j$ 的时候可以停在停机坪上，所以：$s1_i ← s1_i + 1$。

国际同理。

最后再统计 $s1$ 和 $s2$ 的前缀和，枚举分配 $0\sim n$ 个机位给国内，找最大值。

时间复杂度 $O(M\log n + rp)$。（第二层循环不知道会卡多久）

正确性证明

cgy 大佬说我没有正确性证明，那我就来补一个吧。（不过这个东西感觉有点只可意会不可言传，可能我说得不清楚，见谅。）

我们打的优先队列在假设一种情况：有 $m$ 个停机位，从左到右编号为 $1, 2, \ldots, m$。这样可以保证所有飞机都能停到停机位里。

每一次有一个飞机到达的时候，我们就选择最左边的那个机位停飞机。此时，这个机位的编号就是它能停到停机位里所需要的最少的停机位数量。

为什么呢？

因为每一个飞机都在尽量往左边停，如果它停在了右边，就说明它来的时候左边的所有机位都被占领了，它只能停在右边。 我们假设它停在 $j$ 号位，刚才说的那个飞机停在 $i$ 号位，那么，对于任意一个停机位数量 $i\le k < j$，都满足 $i$ 飞机可以停，但 $j$ 飞机不可以停的情况。

它右边的所有飞机都满足这个条件，而它左边的飞机都可以把它当做右边的飞机满足这个条件。所以 $i$ 飞机可以停的条件为 $i\le k$，而我们需要在可以停相同数量的飞机时，尽量节约停机位数量，使得另一个区域的飞机能停更多，所以上述条件成立。

注意

需要把国内和国际的飞机按照到达时间排序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;

const int maxn = (int) 1e5 + 5;

struct node { int s, t; } a[maxn], b[maxn];
struct que { int Time, num; };
int n, tot, m1, m2, ans, s1[maxn], s2[maxn], sum1[maxn], sum2[maxn];
bool is_zhan[maxn];
priority_queue <que> q;

bool cmp(node x, node y) { return x.s < y.s; }
bool operator<(const que x, const que y) { return x.Time > y.Time; }

int main() {
    //freopen("airport.in", "r", stdin);
    //freopen("airport.out", "w", stdout);
    scanf("%d %d %d", &n, &m1, &m2);
    for(int i = 1; i <= m1; i++) scanf("%d %d", &a[i].s, &a[i].t);
    for(int i = 1; i <= m2; i++) scanf("%d %d", &b[i].s, &b[i].t);
    stable_sort(a + 1, a + m1 + 1, cmp);
    stable_sort(b + 1, b + m2 + 1, cmp);
    //国内
    for(int i = 1; i <= m1; i++) {
        while(!q.empty() && q.top().Time < a[i].s) {
            is_zhan[q.top().num] = 0;
            q.pop();
        }
        tot = 1;
        while(is_zhan[tot]) ++tot;
        is_zhan[tot] = 1;
        ++s1[tot];
        que qwq;
        qwq.Time = a[i].t;
        qwq.num = tot;
        q.push(qwq);
    }
    memset(is_zhan, 0,sizeof(is_zhan));
    while(!q.empty()) q.pop();
    //国际 
    for(int i = 1; i <= m2; i++) {
        while(!q.empty() && q.top().Time < b[i].s) {
            is_zhan[q.top().num] = 0;
            q.pop();
        }
        tot = 1;
        while(is_zhan[tot]) ++tot;
        is_zhan[tot] = 1;
        ++s2[tot];
        que qwq;
        qwq.Time = b[i].t;
        qwq.num = tot;
        q.push(qwq);
    }
    //汇总 
    for(int i = 1; i <= n; i++) sum1[i] = sum1[i - 1] + s1[i];
    for(int i = 1; i <= n; i++) sum2[i] = sum2[i - 1] + s2[i];
    for(int i = 0; i <= n; i++) ans = max(ans, sum1[i] + sum2[n - i]);
    printf("%d", ans);
    return 0;
}

优化

这个代码在洛谷和官方吸氧能过，但是我们 OJ 自造的毒瘤数据过不了（而且教练死活不开 O2）所以就有了优化。

大家注意到上面代码的一句：

1
while(is_zhan[tot]) ++tot;

这玩意儿要是数据毒瘤能把时间复杂度卡到 $O(Mn\log n)$。

于是我们可以再开一个优先队列存没有被占用的机位，按照编号从小到大排序，每次只需要从这个序列里取第一个就行了。

所以 $is\_zhan$ 数组就这么退役了 qwq。

时间复杂度 $O(M\log n)$，跑得飞快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#pragma G++ optimize(2)
using namespace std;

const int maxn = (int) 1e5 + 5;

struct node { int s, t; } a[maxn], b[maxn];
struct que { int Time, num; };
int n, tot, m1, m2, ans, s1[maxn], s2[maxn], sum1[maxn], sum2[maxn];
priority_queue <que> q;
priority_queue <int, vector <int>, greater <int> > no_zhan;

bool cmp(node x, node y) { return x.s < y.s; }
bool operator < (const que x, const que y) { return x.Time > y.Time; }

int main() {
    scanf("%d %d %d", &n, &m1, &m2);
    for(int i = 1; i <= m1; i++) scanf("%d %d", &a[i].s, &a[i].t);
    for(int i = 1; i <= m2; i++) scanf("%d %d", &b[i].s, &b[i].t);
    stable_sort(a + 1, a + m1 + 1, cmp);
    stable_sort(b + 1, b + m2 + 1, cmp);
    //国内
    for(int i = 1; i <= m1; i++) no_zhan.push(i);
    for(int i = 1; i <= m1; i++) {
        while(!q.empty() && q.top().Time < a[i].s) {
            no_zhan.push(q.top().num);
            q.pop();
        }
        tot = no_zhan.top();
        no_zhan.pop();
        ++s1[tot];
        que qwq;
        qwq.Time = a[i].t;
        qwq.num = tot;
        q.push(qwq);
    }
    while(!q.empty()) q.pop();
    while(!no_zhan.empty()) no_zhan.pop();
    //国际 
    for(int i = 1; i <= m2; i++) no_zhan.push(i);
    for(int i = 1; i <= m2; i++) {
        while(!q.empty() && q.top().Time < b[i].s) {
            no_zhan.push(q.top().num);
            q.pop();
        }
        tot = no_zhan.top();
        no_zhan.pop();
        ++s2[tot];
        que qwq;
        qwq.Time = b[i].t;
        qwq.num = tot;
        q.push(qwq);
    }
    //汇总 
    for(int i = 1; i <= n; i++) sum1[i] = sum1[i - 1] + s1[i];
    for(int i = 1; i <= n; i++) sum2[i] = sum2[i - 1] + s2[i];
    for(int i = 0; i <= n; i++) ans = max(ans, sum1[i] + sum2[n - i]);
    printf("%d", ans);
    return 0;
}