[CSP-S 2021] 廊桥分配

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

先分别模拟国内和国际航班在最小可用廊桥编号策略下的收益前缀和，再枚举两区廊桥数量分配取最大值。

OJ: luogu

题目 ID: P7913

难度:普及+/提高-

标签:模拟贪心优先队列

创建: 2026-07-06 08:46

更新: 2026-10-07 10:45

形式化题目

机场有 $n$ 个廊桥，需分配给国内区和国际区。国内航班只能用国内区廊桥，国际航班只能用国际区廊桥。每个区内部按到达时间先到先得：有空闲廊桥就停靠，否则停远机位。求使停靠廊桥的飞机总数最大的分配方案。

解法路线

题面给出了三个真实的分数档位：

档位	真实约束	做法	瓶颈
$20\%$	$n \leqslant 100,\ m_1+m_2 \leqslant 100$	枚举分配再逐区模拟	$n \cdot m \log m$
$40\%$	$n \leqslant 5000,\ m_1+m_2 \leqslant 5000$	收益前缀和 + 枚举分配	无
$100\%$	$n \leqslant 10^5,\ m_1+m_2 \leqslant 10^5$	同上	无

$20\%$ 用暴力枚举， $40\%$ 引入收益前缀和消除重复模拟， $100\%$ 沿用同一算法、仅扩大数组规模。每层代码都能独立提交、逐层拿分。

暴力解法： $n \leqslant 100$

适用范围

$20\%$ 的数据满足 $n \leqslant 100,\ m_1+m_2 \leqslant 100$ ，可以枚举所有分配方案再逐区模拟。

思路

枚举国内区分到 $i$ 个廊桥（ $0 \leqslant i \leqslant n$ ），分别模拟国内和国际航班的先到先得过程，取最大值。模拟时用最小堆维护空闲廊桥编号和正在占用的廊桥。

代码

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
77
78
79
80
81
82
83
84
85
86
87/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:39
 * update_at: 2026-10-01 22:39
 */
// subtask_20.cpp：20% 数据 n ≤ 100, m1+m2 ≤ 100，枚举国内分几个廊桥再模拟。
// 时间 O(n · m log m)，空间 O(m)。覆盖 20% 档。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 105;

// 航班：抵达时刻和离开时刻。
struct Flight {
    int arrive;
    int leave;
};

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

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

// 模拟一个区域分配 bridge_count 个廊桥，返回能接的航班数。
int simulate(Flight flights[], ll m, ll 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 (ll i = 1; i <= bridge_count; i++) {
        free_bridge.push((int)i);
    }

    int answer = 0;
    for (ll 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 (ll i = 1; i <= m1; i++) {
        cin >> domestic[i].arrive >> domestic[i].leave;
    }
    for (ll i = 1; i <= m2; i++) {
        cin >> international_flight[i].arrive >> international_flight[i].leave;
    }

    // 先排序一次，后续 simulate 不会改变顺序。
    sort(domestic + 1, domestic + m1 + 1, cmp_flight);
    sort(international_flight + 1, international_flight + m2 + 1, cmp_flight);

    // 枚举国内分几个廊桥，取两种分配的最大值。
    int answer = 0;
    for (ll domestic_bridge = 0; domestic_bridge <= n; domestic_bridge++) {
        int now = simulate(domestic, m1, domestic_bridge)
                + simulate(international_flight, m2, n - domestic_bridge);
        answer = max(answer, now);
    }

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

复杂度与瓶颈

时间 $O(n \cdot m \log m)$ 。 $n = 100,\ m = 100$ 时很快，但 $n = 5000$ 时就要做 $5000$ 次模拟，太慢。

子任务解法： $n \leqslant 5000$

适用范围

$40\%$ 的数据满足 $n \leqslant 5000,\ m_1+m_2 \leqslant 5000$ 。暴力的 $n$ 次重复模拟太慢，需要换成一次模拟 + 前缀和。

思路

关键观察：对同一个区域，可以一次模拟出"分配 $i$ 个廊桥能接多少航班"（ $1 \leqslant i \leqslant n$ ）。

模拟时始终把飞机分配给编号最小的空闲廊桥。设某架飞机被分到编号 $x$ ，说明编号小于 $x$ 的廊桥都正被占用；若只有 $x-1$ 个廊桥，它就无法停靠。因此编号 $x$ 被使用的次数就是"第 $x$ 个廊桥额外贡献的航班数"。

对每个区域做一次扫描：按到达时间排序，用最小堆维护空闲廊桥编号和正在占用的廊桥，每次取最小空闲编号分配并统计使用次数，最后做前缀和得到 $sum[i]$ 。

国内区得 $A[i]$ ，国际区得 $B[i]$ ，枚举国内分 $i$ 个廊桥，答案为 $\max(A[i] + B[n-i])$ 。

相比 $20\%$ 暴力，这里不再对每个分配重新模拟，而是复用一次模拟的前缀和结果。

代码

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 23:21
 * update_at: 2026-10-01 23:21
 */
// subtask_40.cpp：40% 数据 n ≤ 5000, m1+m2 ≤ 5000，用收益前缀和 + 枚举分配。
// 核心思路：对每个区域一次模拟出"分配 i 个廊桥能接多少航班"的前缀和，再枚举分配取最大值。
// 相比 20% 暴力，不再对每个分配重新模拟，而是复用前缀和，时间降到 O(m log m + n)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 5005;

// 航班：抵达时刻和离开时刻（均 ≤ 10^8，int 足够）。
struct Flight {
    int arrive;
    int leave;
};

ll n, m1, m2;
Flight domestic[MAXN], international_flight[MAXN];
int cnt_domestic[MAXN], cnt_international[MAXN]; // 分配 i 个廊桥时新增接的航班数
int sum_domestic[MAXN], sum_international[MAXN]; // 前缀和：分配 ≤ i 个廊桥共接多少航班

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

// 模拟一个区域：分配最多 n 个廊桥，用最小可用编号策略，
// 统计每个廊桥编号各接了多少航班，最后做前缀和。
void calc(Flight flights[], ll 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;

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

    for (ll 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));
        }
    }

    // 前缀和：result[i] = 分配 ≤ i 个廊桥共接多少航班。
    for (ll 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 (ll i = 1; i <= m1; i++) {
        cin >> domestic[i].arrive >> domestic[i].leave;
    }
    for (ll 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);

    // 枚举国内分 i 个廊桥，国际分 n-i 个，取最大值。
    int ans = 0;
    for (ll i = 0; i <= n; i++) {
        ans = max(ans, sum_domestic[i] + sum_international[n - i]);
    }
    cout << ans << '\n';

    return 0;
}

复杂度与瓶颈

时间 $O((m_1+m_2)\log(m_1+m_2) + n)$ ，空间 $O(n + m_1 + m_2)$ 。 $n = 5000$ 时轻松通过。 $100\%$ 档沿用同一算法，仅需把数组开到 $10^5$ 。

正解

关键观察

与 $40\%$ 档完全相同：一次模拟出每个区域的收益前缀和，再枚举分配。 $100\%$ 和 $40\%$ 的算法完全相同，唯一区别是数据规模。

思路

对每个区域：按到达时间排序，用最小堆维护空闲廊桥编号和正在占用的廊桥，每次取最小空闲编号分配，统计每个编号被使用次数；
做前缀和，得到 $sum[i]$ ：给这个区域 $i$ 个廊桥时能接多少航班；
国内区得 $A[i]$ ，国际区得 $B[i]$ ，枚举国内分 $i$ 个廊桥，答案为 $\max(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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-01 22:39
 * update_at: 2026-10-01 22:39
 */
// main.cpp：满分做法，用最小可用廊桥编号模拟每个区域，统计分配 i 个廊桥能接多少航班。
// 核心思路：先对每个区域独立算出"分配 i 个廊桥能接的航班数"前缀和，再枚举国内/国际分几个廊桥取最大值。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;

// 航班：抵达时刻和离开时刻（均 ≤ 10^8，int 足够）。
struct Flight {
    int arrive;
    int leave;
};

ll n, m1, m2; // 廊桥总数、国内航班数、国际航班数
Flight domestic[MAXN], international_flight[MAXN];
int cnt_domestic[MAXN], cnt_international[MAXN]; // 分配 i 个廊桥时新增接的航班数
int sum_domestic[MAXN], sum_international[MAXN]; // 前缀和：分配 ≤ i 个廊桥共接多少航班

// 按抵达时刻排序。
bool cmp_flight(const Flight &a, const Flight &b) {
    return a.arrive < b.arrive;
}

// 模拟一个区域：分配最多 n 个廊桥，用最小可用编号策略，
// 统计每个廊桥编号各接了多少航班，最后做前缀和。
void calc(Flight flights[], ll 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;

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

    for (ll 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));
        }
    }

    // 前缀和：result[i] = 分配 ≤ i 个廊桥共接多少航班。
    for (ll 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 (ll i = 1; i <= m1; i++) {
        cin >> domestic[i].arrive >> domestic[i].leave;
    }
    for (ll 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);

    // 枚举国内分 i 个廊桥，国际分 n-i 个，取最大值。
    int ans = 0;
    for (ll i = 0; i <= n; i++) {
        ans = max(ans, sum_domestic[i] + sum_international[n - i]);
    }
    cout << ans << '\n';

    return 0;
}

复杂度

时间复杂度： $O((m_1+m_2)\log(m_1+m_2) + n)$ 。
空间复杂度： $O(n + m_1 + m_2)$ 。

总结

本题的关键是把"分配廊桥数量"和"区内先到先得模拟"解耦：先分别算出每个区域在不同廊桥数量下的收益前缀和，再枚举合并。区内模拟必须使用最小可用廊桥编号，这样每个编号的使用次数才能做前缀和，表示不同廊桥数量下的答案。

三个分数档位串起来是一条"从重复模拟到前缀和"的路线：暴力枚举分配再逐区模拟 → 一次模拟 + 前缀和复用 → 扩大数组规模。真正需要记住的是"最小可用编号策略使得每个编号的使用次数可做前缀和"这一关键观察。

本文的 main.cpp 已用逐区模拟版 brute.cpp 进行 300 组随机对拍；subtask_40.cpp 也已对拍通过。

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] 廊桥分配

目录

形式化题目

解法路线

暴力解法：n⩽100n \leqslant 100n⩽100

适用范围

思路

代码

复杂度与瓶颈

子任务解法：n⩽5000n \leqslant 5000n⩽5000

适用范围

思路

代码

复杂度与瓶颈

正解

关键观察

思路

代码

复杂度

总结

暴力解法： $n \leqslant 100$

子任务解法： $n \leqslant 5000$