2021 廊桥分配 · 方案一枚举分配数模拟

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 1910 字

n 座廊桥分给两个机场（国内 m1 架、国际 m2 架飞机）

2021
贪心

正文

// CSP-S 2021 复赛 T1 · 廊桥分配（方案一：枚举分配数 + 逐次模拟）
// 原题：https://oj.yecheng.tv/p/CSPS2021A
// 题意：n 座廊桥分给两个机场（国内 m1 架、国际 m2 架飞机），飞机
//       [a,b] 时段占一座廊桥，到站时取"当前空闲中编号最小"的廊桥，
//       没有空闲则无法停靠。求一种分配使两机场停靠总数最大。
// 思路（枚举 + 模拟）：
//   枚举给机场 1 分 x 座廊桥（机场 2 得 n-x），对每个 x：
//   - 用 multiset<pair<离开时刻, 廊桥编号>> 模拟：飞机按到达排序，
//     弹出所有已离开的，取最小编号空闲廊桥；
//   - 统计两机场各自停靠数，答案取 max。
//   每个 x 一遍 O(m log m)，总 O(n · m log m)：n, m ≤ 5000 部分
//   分稳过；n = 1e5 会超时（见方案二）。
// 复杂度：O(n · (m1+m2) log)。
// 易错点：
//   1. 飞机必须按到达时刻排序后处理；
//   2. 占用中的廊桥在 b 时刻是否已释放按题面（b 时刻后即可用）；
//   3. 空闲廊桥取编号最小者，multiset 存 (时刻, 编号) 或双集合。
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;

int n, m1, m2;
pair<int,int> A[100005], B[100005];

long long simulate(int bridges, int m, pair<int,int>* v) {
    if (bridges == 0) return 0;
    multiset<pair<int,int> > busy;     // (释放时刻, 廊桥编号)
    multiset<int> freeB;
    for (int i = 1; i <= bridges; i++) freeB.insert(i);
    long long cnt = 0;
    for (int i = 0; i < m; i++) {
        while (!busy.empty() && busy.begin()->first <= v[i].first) {
            freeB.insert(busy.begin()->second);
            busy.erase(busy.begin());
        }
        if (freeB.empty()) continue;
        int b = *freeB.begin();
        freeB.erase(freeB.begin());
        busy.insert(make_pair(v[i].second, b));
        cnt++;
    }
    return cnt;
}

int main() {
    freopen("airport.in", "r", stdin);
    freopen("airport.out", "w", stdout);
    scanf("%d%d%d", &n, &m1, &m2);
    for (int i = 0; i < m1; i++) scanf("%d%d", &A[i].first, &A[i].second);
    for (int i = 0; i < m2; i++) scanf("%d%d", &B[i].first, &B[i].second);
    sort(A, A + m1);
    sort(B, B + m2);
    long long ans = 0;
    for (int x = 0; x <= n; x++) {
        long long c1 = simulate(x, m1, A);
        long long c2 = simulate(n - x, m2, B);
        ans = max(ans, c1 + c2);
    }
    printf("%lld\n", ans);
    return 0;
}

2021 廊桥分配 · 方案一 枚举分配数模拟

正文

CSP-S 标程 · 复赛真题的其它内容

2021 廊桥分配 · 方案一枚举分配数模拟