2021年CSP-S廊桥分配问题解析（洛谷P7913）：基于贪心算法与优先级队列的解题思路

rhsgfswg

一、题目解读

2021年CSP-S中的“廊桥分配”（洛谷P7913）是一个经典的资源分配问题。题目要求处理n个航班，每个航班有到达和离开时间，需在m1到m2个廊桥的限制下，计算使用不同数量的廊桥时能服务的**航班数。核心在于高效分配廊桥资源，避免时间冲突，同时满足数量限制。

二、解题思路

采用贪心策略与优先级队列优化：

1. 航班排序：按到达时间升序排列，确保处理顺序符合时间逻辑。

2. 动态分配：使用两个优先队列——available存储当前可用廊桥的释放时间，in_use存储正在使用的廊桥及释放时间。

3. 分配逻辑：

    优先使用已释放的廊桥（时间不冲突时）；

    若无可用廊桥且剩余廊桥数未满，新建分配。

4. 前缀和优化：计算各廊桥数量的前缀和，便于快速查询不同k值下的**服务数。

三、解题步骤

1. 输入与预处理：读取航班数据，按到达时间排序。

2. 初始化队列：available为空，in_use记录当前分配状态。

3. 循环分配：

    释放过期廊桥（到达时间前已完成的航班）；

    若available不空，分配最小释放时间的廊桥；

    否则若廊桥数未满，新建分配。

4. 前缀和计算：累加各廊桥服务数，生成最终结果。

四、代码与注释

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_flights(n);
    
69.     for (int i = 0; i < n; ++i) {
    
70.         cin >> domestic_flights[i].first >> domestic_flights[i].second;
    
71.     }
    
72.     vector<int> max_flights = calculate_max_flights(domestic_flights, m2);
    
73.    
    
74.     for (int i = m1; i <= m2; ++i) {
    
75.         cout << max_flights[i] << ';
    
76.     }
    
77.     cout << endl;
    
78.    
    
79.     return 0;
    
80. }

复制代码

五、总结

该算法通过优先级队列高效管理廊桥状态，结合贪心思想优先分配可用资源，避免回溯。前缀和的应用进一步简化了结果查询过程。时间复杂度为O(nlogn)，适合处理大规模数据。关键点在于对资源释放时间的动态维护与分配优先级判断。

来源：2021年CSP-S廊桥分配问题解析（洛谷P7913）：基于贪心算法与优先级队列的解题思路