2021 廊桥分配 · 方案二预处理归属加前缀和

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

一次扫描预处理每个 x 的归属，前缀和 O(1) 查询

2021
贪心

正文

// CSP-S 2021 复赛 T1 · 廊桥分配（方案二：预处理归属 + 前缀和，满分）
// 原题：https://oj.yecheng.tv/p/CSPS2021A
// 题意：同方案一（n, m1+m2 ≤ 1e5，需满分）。
// 思路（一遍预处理每个 x 的停靠数）：
//   关键观察：给定 w 座廊桥，哪架飞机能停与 w 有关，但"占用序列"
//   有递推结构：贪心给每架飞机分配"最小编号空闲廊桥"时，廊桥 j 被
//   谁占用只依赖编号 < j 的廊桥状态。于是：
//   1. 用"空廊桥小根堆 + 忙廊桥小根堆"按到达序贪心，但记录每架
//      停靠飞机所用的廊桥编号 j → cnt1[j]++（该编号在本轮被使用的
//      次数）；
//   2. 关键结论：给机场 1 分 x 座时，停靠总数 = Σ_{j≤x} cnt1[j]
//      （廊桥 j 的使用次数与 x 无关——分配过程是"最小可用编号"，
//      前 x 座的使用序列与全量模拟一致）。对机场 2 同理。
//   3. 预处理 cnt1、cnt2 的前缀和，答案 = max_x (S1[x] + S2[n-x])。
// 复杂度：O((m1+m2) log(n))。
// 易错点：
//   1. 廊桥"编号最小"是分配规则，必须用编号堆而不是任意空闲；
//   2. cnt 的语义是"廊桥 j 在整个时间线上被占用的架次"；
//   3. 两机场分开处理；x 从 0 到 n 全枚举取 max。
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

int n, m1, m2;
pair<int,int> A[100005], B[100005];
int cnt1[100005], cnt2[100005];
long long s1[100005], s2[100005];

void solve(int m, pair<int,int>* v, int* cnt) {
    priority_queue<int, vector<int>, greater<int> > freeB;
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > busy;
    for (int j = 1; j <= n; j++) freeB.push(j);
    for (int i = 0; i < m; i++) {
        while (!busy.empty() && busy.top().first <= v[i].first) {
            freeB.push(busy.top().second);
            busy.pop();
        }
        if (freeB.empty()) continue;
        int b = freeB.top();
        freeB.pop();
        cnt[b]++;
        busy.push(make_pair(v[i].second, b));
    }
}

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);
    solve(m1, A, cnt1);
    solve(m2, B, cnt2);
    for (int j = 1; j <= n; j++) {
        s1[j] = s1[j - 1] + cnt1[j];
        s2[j] = s2[j - 1] + cnt2[j];
    }
    long long ans = 0;
    for (int x = 0; x <= n; x++) ans = max(ans, s1[x] + s2[n - x]);
    printf("%lld\n", ans);
    return 0;
}

2021 廊桥分配 · 方案二 预处理归属加前缀和

正文

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

2021 廊桥分配 · 方案二预处理归属加前缀和