2021年CSP-S廊桥分配（洛谷P7913）：贪心算法与优先队列实战 4个月前

一、问题背景分析

2021年CSP-S竞赛的廊桥分配问题要求优化分配有限廊桥资源，最大化服务国内和国际航班数量。题目核心是处理两类航班的起降时间冲突，通过动态调度实现资源高效利用。

二、核心算法设计

1. 数据结构选择

copy
// 优先队列存储可用廊桥编号（按编号排序）
priority_queue<int, vector<int>, greater<int>> available;
// 优先队列存储使用中廊桥的释放时间和编号（按时间排序）
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> in_use;

2. 航班处理流程

1. 时间排序：所有航班按到达时间升序排列
2. 资源释放：检查并回收已完成服务的廊桥
3. 资源分配：
4. • 优先分配已释放的廊桥
   • 若无可用则分配新廊桥（不超过上限）

copy
while (!in_use.empty() && in_use.top().first <= arrive) {
    available.push(in_use.top().second);
    in_use.pop();
}

3. 动态统计结果

通过前缀和数组记录不同廊桥数量下的服务能力：

copy
vector<int> res(max_bridges + 1, 0);
//...分配时更新对应廊桥计数
if (bridge <= max_bridges) {
    res[bridge]++;
}
//...最后计算前缀和
for (int i = 1; i <= max_bridges; ++i) {
    res[i] += res[i - 1];
}

三、完整代码解析

copy
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

// 计算使用k个廊桥时能服务的最大航班数
vector<int> calculate_max_flights(const vector<pair<int, int>>& flights, int max_bridges) {
    vector<int> res(max_bridges + 1, 0);
    if (flights.empty()) return res;

    // 按到达时间排序航班
    vector<pair<int, int>> sorted_flights = flights;
    sort(sorted_flights.begin(), sorted_flights.end());

    // 优先队列存储可用廊桥的释放时间
    priority_queue<int, vector<int>, greater<int>> available;
    // 优先队列存储正在使用的廊桥的释放时间
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> in_use;

    int count = 0;
    for (const auto& flight : sorted_flights) {
        int arrive = flight.first;
        int depart = flight.second;

        // 释放已经完成的廊桥
        while (!in_use.empty() && in_use.top().first <= arrive) {
            available.push(in_use.top().second);
            in_use.pop();
        }

        // 如果有可用廊桥，则分配
        if (!available.empty()) {
            int bridge = available.top();
            available.pop();
            in_use.push({depart, bridge});
            count++;
            if (bridge <= max_bridges) {
                res[bridge]++;
            }
        }
        // 如果没有可用廊桥但还有未分配的廊桥，则分配新的
        else if (in_use.size() < max_bridges) {
            int bridge = in_use.size() + 1;
            in_use.push({depart, bridge});
            count++;
            if (bridge <= max_bridges) {
                res[bridge]++;
            }
        }
    }

    // 计算前缀和
    for (int i = 1; i <= max_bridges; ++i) {
        res[i] += res[i - 1];
    }

    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m1, m2;
    cin >> n >> m1 >> m2;

    vector<pair<int, int>> domestic(m1), international(m2);
    for (int i = 0; i < m1; ++i) {
        cin >> domestic[i].first >> domestic[i].second;
    }
    for (int i = 0; i < m2; ++i) {
        cin >> international[i].first >> international[i].second;
    }

    // 计算国内和国际航班在不同廊桥数量下的最大服务数
    auto domestic_res = calculate_max_flights(domestic, n);
    auto international_res = calculate_max_flights(international, n);

    // 寻找最优分配方案
    int max_total = 0;
    for (int i = 0; i <= n; ++i) {
        int j = n - i;
        if (i < 0 || j < 0) continue;
        int total = domestic_res[i] + international_res[j];
        if (total > max_total) {
            max_total = total;
        }
    }

    cout << max_total << endl;

    return 0;
}

来源：竞赛学习