真题解析:P7913 [CSP-S 2021] 廊桥分配(贪心·优先队列·前缀和)

题目来源：洛谷 P7913 [CSP-S 2021] 廊桥分配

一、题意速览

机场有 n 个廊桥，分属两个区域：国内区和国际区。国内航班只能停在国内区的廊桥，国际航班只能停在国际区的廊桥。

每架飞机有一个到达时刻和一个离开时刻，在这两个时刻之间它会占着一个廊桥。廊桥的使用遵循"先到先得"原则：

• 一架飞机抵达后，如果它所属的区域里还有空闲廊桥，就停进廊桥；
• 如果该区域廊桥都被占了，它就只能停在远机位（远机位数量充足，不会限制航班）。

我们要做的一件事，是把这 n 个廊桥分配给两个区域（国内区 k 个、国际区 n−k 个），使得最终能停进廊桥的飞机总数最多。

注意题目一个隐藏条件：机场只有一条跑道，任意两架飞机不会同时到达，所以按到达时刻逐架处理即可。

二、输入输出样例

样例输入 #1

3 5 41 53 86 109 1413 182 114 157 1712 16

样例输出 #1

样例解释 #1：把 3 个廊桥按"国内区 2 个、国际区 1 个"分配时，能停进廊桥的飞机最多，一共 7 架。

样例输入 #2

2 4 620 3040 5021 2241 421 192 183 45 67 89 10

样例输出 #2

三、考察知识点

• 区间调度模拟：按时间顺序处理每架航班的到达与离开，维护廊桥的占用与释放状态。
• 双优先队列配合：一个堆管理"正在占用"（按离开时间），另一个堆管理"空闲编号"（按编号大小），实现 O(log m) 的分配操作。
• 无限廊桥→前缀和优化：不直接枚举每种廊桥数量重跑模拟，而是先假设廊桥无限跑一遍贪心，通过 cnt 数组的前缀和一次性得到所有 f(k)，将复杂度从 O(n·m) 降到 O(m log m + n)。
• 分类枚举取最优：两区域独立处理后，枚举每种分配方案 i（0 到 n）取 max{f1(i) + f2(n−i)}。

四、核心思路

两个区域互不影响，可以拆开分别计算。

以国内区为例，设 f1(k) 表示"给国内区分配 k 个廊桥时，最多能停几架国内航班"。同理国际区有 f2(k)。那么把 n 个廊桥按"国内 i 个、国际 n−i 个"分配时，总停靠数就是 f1(i) + f2(n−i)。只要算出所有 f1、f2，再 O(n) 枚举 i 取最大值即可：

ans = max{ f1(i) + f2(n - i) }   (0 ≤ i ≤ n)

难点在于：f(k) 怎么算才不超时？

朴素做法会超时：对每一个 i（0 到 n）都独立跑一遍贪心模拟，复杂度 O(n·(m1+m2))。而 n、m1、m2 都可到 10⁵，乘积达到 10¹⁰，必然 TLE。

关键优化：先不要去管"只有 k 个廊桥"这个限制。我们假设廊桥数量无限，按同样的贪心规则（每次分给编号最小的空闲廊桥）把每架飞机都安顿好，并记录下"编号为 id 的廊桥一共停了几架飞机"，记作 cnt[id]。

然后有一个核心结论：

给 k 个廊桥时，能停的航班总数 = 所有编号 ≤ k 的廊桥停的航班之和 = cnt 数组的前缀和 prefix[k]。

理由是：贪心始终把飞机塞进"当前编号最小的空闲廊桥"，所以一座编号较大的廊桥被使用的前提，是前面所有更小编号的廊桥都已经被占满。换句话说，限制"只能用编号 1..k 的廊桥"，恰好等价于"只分配 k 个廊桥"。编号大于 k 的廊桥在受限场景下根本不会出现（退化成远机位），自然不算。

于是只需要跑一遍无限廊桥的贪心，得到 cnt 数组，做一次前缀和，就同时拿到了所有 f(k)。两个区域各跑一遍，再枚举分配即可。复杂度从 O(n·m) 降到 O((m1+m2)·log(m1+m2) + n)。

五、贪心分配怎么模拟

对某一区域的航班，先按到达时刻升序排序（题目保证到达时刻互不相同，排序稳定）。然后用两个小根堆配合模拟：

• 占用堆 occ_pq：存当前正在占用廊桥的飞机，按 (离开时间, 廊桥编号) 升序，堆顶是"最早离开"的那架。
• 空闲堆 free_pq：存当前空闲廊桥的编号，按编号升序，堆顶是"编号最小"的空闲廊桥。

逐架处理航班（到达时刻 arrive、离开时刻 leave）：

1. 先把占用堆里所有"离开时间 < 当前航班到达时间"的飞机弹出，它们的廊桥腾空了，把编号丢进空闲堆。
2. 如果空闲堆为空（没有现成廊桥可用），就新开一座廊桥（编号 next_id++，这正是"假设无限廊桥"的体现）。
3. 从空闲堆取编号最小的廊桥 id 分配给这架飞机，把 (leave, id) 压入占用堆，并 cnt[id]++。

每架航班各做一次堆操作，复杂度 O(m log m)。

注意 priority_queue 默认是大根堆，要小根堆需写明 greater<T>（或 greater<pair<int,int>>）。

六、前缀和与枚举分配

跑完一遍贪心后，cnt[id] 存着每座廊桥停的航班数。做前缀和：

prefix[k] = prefix[k-1] + cnt[k]

prefix[k] 就是"分配 k 个廊桥时最多能停的航班数"，即我们要的 f(k)。

枚举 i 从 0 到 n，取 f1(i) + f2(n−i) 的最大值就是答案。这里有个细节：i 可能超过该区域实际航班数 m1，此时再多廊桥也停不了更多飞机，直接用 prefix 的末项（全部航班都能停）即可。

七、复杂度分析

• 排序：O(m log m)
• 贪心模拟：每架航班各一次堆操作，O(m log m)
• 前缀和 + 枚举：O(m + n)

总复杂度 O((m1+m2)·log(m1+m2) + n)。在 m1、m2、n 都到 10⁵ 时，量级约 10⁶，远在 1 秒安全线（约 10⁸）以内。

八、参考代码

#include <bits/stdc++.h>using namespace std;int n, m1, m2;// 预处理：v 已按到达时间升序排序// 返回 prefix[k] = 分配 k 个廊桥时最多能停的航班数vector<int> solve(const vector<pair<int, int>>& v){    int m = v.size();    // cnt[id] 记录编号为 id 的廊桥停了几架航班    vector<int> cnt(m + 1, 0);    // occ_pq：正在使用的廊桥，小根堆，按 (离开时间, 廊桥编号) 排序    priority_queue<pair<int, int>, vector<pair<int, int>>,                   greater<pair<int, int>>> occ_pq;    // free_pq：空闲廊桥编号，小根堆，每次取编号最小的    priority_queue<int, vector<int>, greater<int>> free_pq;    int next_id = 1;  // 下一个新开廊桥的编号（假设无限廊桥）    for (const auto& p : v) {        int arrive = p.first;   // 到达时间        int leave  = p.second;  // 离开时间        // ① 释放所有在当前航班到达前已经离开的廊桥        while (!occ_pq.empty() && occ_pq.top().first < arrive) {            free_pq.push(occ_pq.top().second);            occ_pq.pop();        }        // ② 没有空闲廊桥就新开一个（无限廊桥假设）        if (free_pq.empty()) {            free_pq.push(next_id++);        }        // ③ 分配编号最小的空闲廊桥        int id = free_pq.top();        free_pq.pop();        // ④ 占用该廊桥，记录离开时间与该廊桥停的航班数        occ_pq.push({leave, id});        cnt[id]++;    }    // 前缀和：prefix[k] = 编号 <= k 的所有廊桥停的航班总数    vector<int> prefix(m + 1, 0);    for (int i = 1; i <= m; i++) {        prefix[i] = prefix[i - 1] + cnt[i];    }    return prefix;}int main(){    ios::sync_with_stdio(0);    cin.tie(0);    cin >> n >> m1 >> m2;    // 国内航班、国际航班    vector<pair<int, int>> v1(m1), v2(m2);    for (int i = 0; i < m1; i++) cin >> v1[i].first >> v1[i].second;    for (int i = 0; i < m2; i++) cin >> v2[i].first >> v2[i].second;    // 按到达时间升序排序    sort(v1.begin(), v1.end());    sort(v2.begin(), v2.end());    // 预处理国内外各自的 prefix[k]    auto f1 = solve(v1);    auto f2 = solve(v2);    // 枚举国内 i 个廊桥、国际 n-i 个廊桥，取最大航班数    int ans = 0;    for (int i = 0; i <= n; i++) {        int j = n - i;        int a = (i < (int)f1.size()) ? f1[i] : f1.back();        int b = (j < (int)f2.size()) ? f2[j] : f2.back();        ans = max(ans, a + b);    }    cout << ans;    return 0;}