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

胡志明t

一、问题背景分析

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

二、核心算法设计1. 数据结构选择// 优先队列存储可用廊桥编号（按编号排序）priority_queue<int, vector<int>, greater<int>> available;// 优先队列存储使用中廊桥的释放时间和编号（按时间排序）priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> in_use;2. 航班处理流程

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

while (!in_use.empty() && in_use.top().first <= arrive) {    available.push(in_use.top().second);    in_use.pop();}3. 动态统计结果

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

vector<int> res(max_bridges + 1, 0);//...分配时更新对应廊桥计数if (bridge <= max_bridges) {    res[bridge]++;}//...**计算前缀和for (int i = 1; i <= max_bridges; ++i) {    res += res[i - 1];}三、完整代码解析

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. #include <queue>
   
5. using namespace std;
   
6. 
   
7. // 计算使用k个廊桥时能服务的**航班数
   
8. vector<int> calculate_max_flights(const vector<pair<int, int>>& flights, int max_bridges) {
   
9.     vector<int> res(max_bridges + 1, 0);
   
10.     if (flights.empty()) return res;
    
11.    
    
12.     // 按到达时间排序航班
    
13.     vector<pair<int, int>> sorted_flights = flights;
    
14.     sort(sorted_flights.begin(), sorted_flights.end());
    
15.    
    
16.     // 优先队列存储可用廊桥的释放时间
    
17.     priority_queue<int, vector<int>, greater<int>> available;
    
18.     // 优先队列存储正在使用的廊桥的释放时间
    
19.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> in_use;
    
20.    
    
21.     int count = 0;
    
22.     for (const auto& flight : sorted_flights) {
    
23.         int arrive = flight.first;
    
24.         int depart = flight.second;
    
25.         
    
26.         // 释放已经完成的廊桥
    
27.         while (!in_use.empty() && in_use.top().first <= arrive) {
    
28.             available.push(in_use.top().second);
    
29.             in_use.pop();
    
30.         }
    
31.         
    
32.         // 如果有可用廊桥，则分配
    
33.         if (!available.empty()) {
    
34.             int bridge = available.top();
    
35.             available.pop();
    
36.             in_use.push({depart, bridge});
    
37.             count++;
    
38.             if (bridge <= max_bridges) {
    
39.                 res[bridge]++;
    
40.             }
    
41.         }
    
42.         // 如果没有可用廊桥但还有未分配的廊桥，则分配新的
    
43.         else if (in_use.size() < max_bridges) {
    
44.             int bridge = in_use.size() + 1;
    
45.             in_use.push({depart, bridge});
    
46.             count++;
    
47.             if (bridge <= max_bridges) {
    
48.                 res[bridge]++;
    
49.             }
    
50.         }
    
51.     }
    
52.    
    
53.     // 计算前缀和
    
54.     for (int i = 1; i <= max_bridges; ++i) {
    
55.         res[i] += res[i - 1];
    
56.     }
    
57.    
    
58.     return res;
    
59. }
    
60. 
    
61. int main() {
    
62.     ios::sync_with_stdio(false);
    
63.     cin.tie(nullptr);
    
64.    
    
65.     int n, m1, m2;
    
66.     cin >> n >> m1 >> m2;
    
67.    
    
68.     vector<pair<int, int>> domestic(m1), international(m2);
    
69.     for (int i = 0; i < m1; ++i) {
    
70.         cin >> domestic[i].first >> domestic[i].second;
    
71.     }
    
72.     for (int i = 0; i < m2; ++i) {
    
73.         cin >> international[i].first >> international[i].second;
    
74.     }
    
75.    
    
76.     // 计算国内和国际航班在不同廊桥数量下的**服务数
    
77.     auto domestic_res = calculate_max_flights(domestic, n);
    
78.     auto international_res = calculate_max_flights(international, n);
    
79.    
    
80.     // 寻找**分配方案
    
81.     int max_total = 0;
    
82.     for (int i = 0; i <= n; ++i) {
    
83.         int j = n - i;
    
84.         if (i < 0 || j < 0) continue;
    
85.         int total = domestic_res[i] + international_res[j];
    
86.         if (total > max_total) {
    
87.             max_total = total;
    
88.         }
    
89.     }
    
90.    
    
91.     cout << max_total << endl;
    
92.    
    
93.     return 0;
    
94. }

复制代码

来源：竞赛学习