[CSP-S 2021] 廊桥分配

GitHub 跳转原题关系图返回列表

分别模拟国内和国际航班使用最小可用廊桥编号，再枚举两区廊桥数量分配。

OJ: luogu

题目 ID: P7913

难度:普及+/提高

标签:模拟贪心优先队列

日期: 2026-07-06 08:46

题意

机场一共有 $n$ 个廊桥，要把其中一部分分给国内区，剩下的分给国际区。国内航班只能用国内区廊桥，国际航班只能用国际区廊桥。

每个区内部遵循同一个规则：飞机按到达时间依次处理，如果此时有空闲廊桥，就停靠廊桥；否则只能停远机位。要求选择国内区廊桥数量，使停靠廊桥的飞机总数最大。

思路

最直接的想法是枚举国内区分到 $i$ 个廊桥，再分别模拟国内和国际航班。这个做法很好理解，适合小数据验证：

cpp

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76// brute.cpp：小数据暴力解，枚举国内区分到多少廊桥，再直接模拟先到先得。
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 105;

struct Flight {
    int arrive;
    int leave;
};

int n, m1, m2;
Flight domestic[MAXM], international_flight[MAXM];

bool cmp_flight(const Flight &a, const Flight &b) {
    return a.arrive < b.arrive;
}

int simulate(Flight flights[], int m, int bridge_count) {
    if (bridge_count == 0) {
        return 0;
    }

    sort(flights + 1, flights + m + 1, cmp_flight);

    priority_queue<int, vector<int>, greater<int> > free_bridge;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > busy;
    for (int i = 1; i <= bridge_count; i++) {
        free_bridge.push(i);
    }

    int answer = 0;
    for (int i = 1; i <= m; i++) {
        while (!busy.empty() && busy.top().first < flights[i].arrive) {
            free_bridge.push(busy.top().second);
            busy.pop();
        }

        if (!free_bridge.empty()) {
            int id = free_bridge.top();
            free_bridge.pop();
            answer++;
            busy.push(make_pair(flights[i].leave, id));
        }
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m1 >> m2;
    for (int i = 1; i <= m1; i++) {
        cin >> domestic[i].arrive >> domestic[i].leave;
    }
    for (int i = 1; i <= m2; i++) {
        cin >> international_flight[i].arrive >> international_flight[i].leave;
    }

    int answer = 0;
    for (int domestic_bridge = 0; domestic_bridge <= n; domestic_bridge++) {
        Flight d[MAXM], g[MAXM];
        for (int i = 1; i <= m1; i++) {
            d[i] = domestic[i];
        }
        for (int i = 1; i <= m2; i++) {
            g[i] = international_flight[i];
        }
        int now = simulate(d, m1, domestic_bridge) + simulate(g, m2, n - domestic_bridge);
        answer = max(answer, now);
    }

    cout << answer << '\n';
    return 0;
}

暴力的瓶颈在于：每枚举一个 $i$ ，都要重新模拟两类航班。如果 $n$ 和航班数都是 $10^5$ ，这样会重复做大量相同工作。

关键观察是：对于同一个区域，我们可以一次模拟出“如果有 $1$ 个、 $2$ 个、…、 $n$ 个廊桥，各能接多少航班”。

模拟时，始终把飞机分配给编号最小的空闲廊桥。设某架飞机被分到编号 $x$ ，这表示在它到达时，编号小于 $x$ 的廊桥都正在被占用；如果这个区域只有 $x-1$ 个廊桥，它就无法停靠。因此，编号 $x$ 被使用的次数，可以看成“第 $x$ 个廊桥额外贡献的航班数”。

于是对每个区域做一次扫描：

按到达时间排序所有航班；
用一个小根堆维护已经离开的飞机，把它们占用的廊桥放回空闲集合；
用另一个小根堆维护当前空闲廊桥编号；
每次取最小空闲编号分配，并统计这个编号被使用了几次；
最后做前缀和，得到 $sum[i]$ ：给这个区域 $i$ 个廊桥时能接多少航班。

国内区得到 $A[i]$ ，国际区得到 $B[i]$ 后，枚举国内区分到 $i$ 个廊桥，答案就是：

text

1max(A[i] + B[n - i])

代码

cpp

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
62
63
64
65
66
67
68
69
70
71
72
73// main.cpp：用最小可用廊桥编号模拟每个区域，统计分配 i 个廊桥能接多少航班。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

struct Flight {
    int arrive;
    int leave;
};

int n, m1, m2;
Flight domestic[MAXN], international_flight[MAXN];
int cnt_domestic[MAXN], cnt_international[MAXN];
int sum_domestic[MAXN], sum_international[MAXN];

bool cmp_flight(const Flight &a, const Flight &b) {
    return a.arrive < b.arrive;
}

void calc(Flight flights[], int m, int result[]) {
    sort(flights + 1, flights + m + 1, cmp_flight);

    priority_queue<int, vector<int>, greater<int> > free_bridge;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > busy;

    int limit = min(n, m);
    for (int i = 1; i <= limit; i++) {
        free_bridge.push(i);
    }

    for (int i = 1; i <= m; i++) {
        while (!busy.empty() && busy.top().first < flights[i].arrive) {
            free_bridge.push(busy.top().second);
            busy.pop();
        }

        if (!free_bridge.empty()) {
            int id = free_bridge.top();
            free_bridge.pop();
            result[id]++;
            busy.push(make_pair(flights[i].leave, id));
        }
    }

    for (int i = 1; i <= n; i++) {
        result[i] += result[i - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m1 >> m2;
    for (int i = 1; i <= m1; i++) {
        cin >> domestic[i].arrive >> domestic[i].leave;
    }
    for (int i = 1; i <= m2; i++) {
        cin >> international_flight[i].arrive >> international_flight[i].leave;
    }

    calc(domestic, m1, sum_domestic);
    calc(international_flight, m2, sum_international);

    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, sum_domestic[i] + sum_international[n - i]);
    }
    cout << ans << '\n';

    return 0;
}

复杂度

设总航班数为 $m1 + m2$ 。

每个区域的航班排序复杂度为 $O(m log m)$ ，模拟时每架飞机最多进出堆一次，复杂度也是 $O(m log n)$ 。最后枚举分配数量是 $O(n)$ 。

总时间复杂度为 $O((m1 + m2) \log (m1 + m2) + n)$ ，空间复杂度为 $O(n + m1 + m2)$ 。

总结

本题不要把“分配国内/国际廊桥数量”和“区内先到先得模拟”绑在一起重复做。先分别算出每个区域在不同廊桥数量下的收益，再做一次枚举合并，问题就变成两个收益数组的拼接。

核心实现点是：区内模拟必须使用最小可用廊桥编号，这样每个编号的使用次数才可以做前缀和，表示不同廊桥数量下的答案。

P7913 [CSP-S 2021] 廊桥分配

题目描述

当一架飞机抵达机场时，可以停靠在航站楼旁的廊桥，也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥，因为这样省去了坐摆渡车前往航站楼的周折。然而，因为廊桥的数量有限，所以这样的愿望不总是能实现。

机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。

L 市新建了一座机场，一共有 $n$ 个廊桥。该机场决定，廊桥的使用遵循“先到先得”的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。

现给定未来一段时间飞机的抵达、离开时刻，请你负责将 $n$ 个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。

输入格式

输入的第一行，包含三个正整数 $n, m_1, m_2$ ，分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量。

接下来 $m_1$ 行，是国内航班的信息，第 $i$ 行包含两个正整数 $a_{1, i}, b_{1, i}$ ，分别表示一架国内航班飞机的抵达、离开时刻。

接下来 $m_2$ 行，是国际航班的信息，第 $i$ 行包含两个正整数 $a_{2, i}, b_{2, i}$ ，分别表示一架国际航班飞机的抵达、离开时刻。

每行的多个整数由空格分隔。

输出格式

输出一个正整数，表示能够停靠廊桥的飞机数量的最大值。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

1见附件中的 airport/airport3.in

输出 #3

text

1见附件中的 airport/airport3.ans

说明/提示

【样例解释 #1】

在图中，我们用抵达、离开时刻的数对来代表一架飞机，如 $(1, 5)$ 表示时刻 $1$ 抵达、时刻 $5$ 离开的飞机；用 $\surd$ 表示该飞机停靠在廊桥，用 $\times$ 表示该飞机停靠在远机位。

我们以表格中阴影部分的计算方式为例，说明该表的含义。在这一部分中，国际区有 $2$ 个廊桥， $4$ 架国际航班飞机依如下次序抵达：

首先 $(2, 11)$ 在时刻 $2$ 抵达，停靠在廊桥。
然后 $(4, 15)$ 在时刻 $4$ 抵达，停靠在另一个廊桥。
接着 $(7, 17)$ 在时刻 $7$ 抵达，这时前 $2$ 架飞机都还没离开、都还占用着廊桥，而国际区只有 $2$ 个廊桥，所以只能停靠远机位。
最后 $(12, 16)$ 在时刻 $12$ 抵达，这时 $(2, 11)$ 这架飞机已经离开，所以有 $1$ 个空闲的廊桥，该飞机可以停靠在廊桥。

根据表格中的计算结果，当国内区分配 $2$ 个廊桥、国际区分配 $1$ 个廊桥时，停靠廊桥的飞机数量最多，一共 $7$ 架。

【样例解释 #2】

当国内区分配 $2$ 个廊桥、国际区分配 $0$ 个廊桥时，停靠廊桥的飞机数量最多，一共 $4$ 架，即所有的国内航班飞机都能停靠在廊桥。

需要注意的是，本题中廊桥的使用遵循“先到先得”的原则，如果国际区只有 $1$ 个廊桥，那么将被飞机 $(1, 19)$ 占用，而不会被 $(3, 4)$ 、 $(5, 6)$ 、 $(7, 8)$ 、 $(9, 10)$ 这 $4$ 架飞机先后使用。

【数据范围】

对于 $20 \%$ 的数据， $n \le 100$ ， $m_1 + m_2 \le 100$ 。
对于 $40 \%$ 的数据， $n \le 5000$ ， $m_1 + m_2 \le 5000$ 。
对于 $100 \%$ 的数据， $1 \le n \le {10}^5$ ， $m_1, m_2 \ge 1$ ， $m_1 + m_2 \le {10}^5$ ，所有 $a_{1, i}, b_{1, i}, a_{2, i}, b_{2, i}$ 为数值不超过 ${10}^8$ 的互不相同的正整数，且保证对于每个 $i \in [1, m_1]$ ，都有 $a_{1, i} < b_{1, i}$ ，以及对于每个 $i \in [1, m_2]$ ，都有 $a_{2, i} < b_{2, i}$ 。

【感谢 hack 数据提供】

xingxuxin。
cyslngsul。

[CSP-S 2021] 廊桥分配

目录

题意

思路

代码

复杂度

总结