跳到主要内容

P7913 廊桥分配

感觉模型挺经典的。在微模拟上写了这题，写挂了。

难度普及+/提高
算法优先队列、前缀和
日期2025-11-01

题意简述​

有 nn 个廊桥，m1m_1 个国内航班，m2m_2 个国际航班。每个航班可以安排到廊桥停靠，也可以安排到远机位停靠。每架飞机的抵达时间是 aia_i，出发时间是 bib_i。

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

现在要求你求出如何分配这 nn 个廊桥到国内、国际两个区，使得停靠在廊桥的飞机总数最大，求这个最大值。

范围：1≤n≤105, 1≤m1+m2≤105.1\le n\le10^5,\space1\le m_1+m_2\le10^5.

思路 #1​

这里是我微模拟的思路。

容易想到暴力：我们写一个 check(int x)，检查国内区分配 xx 个廊桥时，停靠在廊桥的飞机总数；然后我们枚举 x=0→nx=0\to n，找到结果最大的分配方案。一种朴素的 check() 方案是：把一架飞机的抵达、出发抽象成两个事件，用结构体记录：

struct FlightEvent {
    int id, t; // 飞机编号、事件发生时间
    bool isArrival; // 是否是抵达事件
}

然后我们按 t 升序排序，枚举所有事件，以国内区分配为例，我们维护一个剩余的国内区廊桥数 rest1。一架新的飞机抵达，如果 rest1 > 0，就标记这架飞机为廊桥停靠，同时 rest1--；一架飞机起飞，如果它是廊桥停靠的，就令 rest1++（同时顺手为这架飞机取消廊桥标记）。

这样，check() 的事件复杂度是 O(n)O(n)，总复杂度就是 O(n2)O(n^2)。根据子任务分配，能拿 40pts40pts。

部分代码
const int MAXN = 1e5;
int n, m1, m2;
struct FlightEvent {
    int id, t;
    bool isArrival;
    bool operator<(const FlightEvent& another) {
        return t < another.t;
    }
} f1[MAXN << 1], f2[MAXN << 1]; // 每趟航班两个事件
bool isVip[MAXN]; // 是否停靠在廊桥
int check(int x) {
    int res = 0;
    int rest1 = x, rest2 = n - x;
    for (int i = 0; i < (m1 << 1); i++) {
        if (f1[i].isArrival && rest1) {
            isVip[f1[i].id] = true, rest1--, res++;
        } else if (!f1[i].isArrival && isVip[f1[i].id]) {
            isVip[f1[i].id] = false, rest1++;
        }
    }
    for (int i = 0; i < (m2 << 1); i++) {
        if (f2[i].isArrival && rest2) {
            isVip[f2[i].id] = true, rest2--, res++;
        } else if (!f2[i].isArrival && isVip[f2[i].id]) {
            isVip[f2[i].id] = false, rest2++;
        }
    }
    return res;
}

思路 #2​

有什么办法快一点呢？实际上有（且仅有）两个优化方向：

  1. 优化 check() 的时间复杂度；
  2. 减少枚举次数。

微模拟时，我选择了方向二，写了三分搜索。很遗憾，三分是假的，本题的答案不是单峰的。实际上正解是向方向一优化的。

受 题解 P7913 [CSP-S 2021] 廊桥分配 启发。

怎么优化 check()？不妨先考虑统计国内区的廊桥飞机总数。我们在计算 check(x+1) 时，能不能复用 check(x) 的结果呢？注意到，国内区廊桥数增加时，只会使得原来远机位的飞机在廊桥停靠，而不会反过来。为什么？因为廊桥的分配机制是 “先到先得”，总是先来的飞机占据廊桥，因而原来远机位的飞机一定在廊桥的飞机之后抵达。

沿着这个思路往下想，当廊桥数从 xx 增加到 x+1x+1 时，一定是原来廊桥占满后第一个抵达的原远机位的飞机获得这个新的廊桥。如何找到这趟航班？如果沿用之前 rest1++ rest1-- 的策略，似乎有点难找。

这里就有一个巧思了：我们给所有廊桥编号（1→n1\to n），每趟国内航班抵达时，为它分配编号最小的廊桥（用优先队列维护；假设 nn 个廊桥全为国内区）；航班出发时，把它对应的廊桥重新加入队列。如果一趟国内航班被分配的廊桥编号为 xx，说明国内区廊桥数 ≥x\ge x 时，该飞机有可用廊桥停靠。

也就是说，当廊桥数从 xx 增加到 x+1x+1 时，新停靠在廊桥的就是那些编号为 xx 的航班。于是我们令 arr[x] 表示被分配的廊桥编号为 xx 的航班总数。那么 arr[1...x] 的前缀和就是国内区有 xx 个廊桥时，停靠在廊桥的国内航班总数。

编码​

似乎我这种写法比原题解的更好理解一点。

用时 911 ms 内存 6.07 MB
/*
* P7913 [CSP-S 2021] 廊桥分配
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
int n, m1, m2;
struct FlightEvent {
    int id, t;
    bool isArrival;
    bool operator<(const FlightEvent& another) {
        return t < another.t;
    }
} f1[MAXN << 1], f2[MAXN << 1]; // 每趟航班两个事件
int jetId[MAXN]; // 航班对应的廊桥编号
int arr1[MAXN], arr2[MAXN];
void solve(const FlightEvent f[], const int m, int arr[]) {
    priority_queue<int, vector<int>, greater<int>> q;
    // 压入所有廊桥
    for (int i = 1; i <= n; i++) q.push(i);
    for (int i = 0; i < (m << 1); i++) {
        if (f[i].isArrival && !q.empty()) {
            // 分配新的廊桥
            jetId[f[i].id] = q.top(), arr[q.top()]++, q.pop();
        } else if (!f[i].isArrival && jetId[f[i].id] != 0) {
            // 把廊桥重新加入队列
            q.push(jetId[f[i].id]), jetId[f[i].id] = 0;
        }
    }
    // 计算前缀和
    for (int i = 1; i <= n; i++) {
        arr[i] += arr[i - 1];
    }
}
int main() {
    cin >> n >> m1 >> m2;
    int a, b;
    for (int i = 0; i < m1; i++) {
        cin >> a >> b;
        f1[i << 1] = { i, a, true };
        f1[i << 1 | 1] = { i, b, false };
    }
    for (int i = 0; i < m2; i++) {
        cin >> a >> b;
        f2[i << 1] = { i, a, true };
        f2[i << 1 | 1] = { i, b, false };
    }
    sort(f1, f1 + (m1 << 1));
    sort(f2, f2 + (m2 << 1));
    solve(f1, m1, arr1);
    solve(f2, m2, arr2);
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, arr1[i] + arr2[n - i]);
    }
    cout << ans << '\n';
    return 0;
}