复赛-1：廊桥分配(airport)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-08-07 18:01:00
 * 最后修改: 2025-10-07 13:50:05
 * 文件描述: 2021年CSP-S复赛，模拟算法，30分
****************************************************************/
#include <bits/stdc++.h>
#include <vector>
using namespace std;

// 定义航班结构体，包含起飞时间和降落时间
struct airTime{
    int b,e; // 航班开始和结束时间
} ;
//计算g个廊桥情况下，飞机有多少可以停靠廊桥
int seved_with_gates(const vector<airTime>& flights,int g ){
    int ans=0;
    if(g==0)return 0;
    vector<int> line(g,-1); // 存储当前使用的廊桥分配情况
    int used = 0; // 已经启用的廊桥条数（<= g） 
     // 遍历所有航班
    for (int j = 0; j < flights.size(); j++) {  
        if (used<g) { // 如果还未分配完所有廊桥
            line[used] = j;
            ++used;
            ++ans;
        } else {
            for (int k = 0; k < g; k++) {
                // 如果当前航班可以使用该廊桥
                if (flights[j].b > flights[line[k]].e) { 
                    line[k] = j; // 更新廊桥分配
                    ans++; // 航班计数增
                    break;
                }
            }
        }
    }
    return ans;
}
// 比较函数，用于按开始时间排序航班
bool compare(airTime a, airTime c){
    return a.b < c.b;
}

int main() {
    int n, dom, inte; // n 表示廊桥数量，dom 表示国内航班数量，inte 表示国际航班数量
    cin >> n >> dom >> inte; // 读取输入值
    
    vector<airTime> Dom(dom); // 存储国内航班信息
    vector<airTime> Inte(inte); // 存储国际航班信息
    
    // 读取所有国内航班信息
    for (int i = 0; i < dom; i++)cin >>Dom[i].b>>Dom[i].e;// 读取航班的开始时间和结束时间
    sort(Dom.begin(), Dom.end(), compare); // 按航班开始时间对国内航班排序
    
    // 读取所有国际航班信息
    for (int i = 0; i < inte; i++)  cin >> Inte[i].b >> Inte[i].e; // 读取航班的开始时间和结束时间
    sort(Inte.begin(), Inte.end(), compare);// 按航班开始时间对国际航班排序
    int anss = 0; // 最终能停靠廊桥的最大航班数量
    // 遍历所有可能的廊桥分配方案
    for (int i = 0; i <= n; i++) {
        int ansi = seved_with_gates(Dom, i); // 国内航班计数
        int ansd=seved_with_gates(Inte, n-i);
        anss = max(anss, ansi + ansd); // 更新最大停靠航班数量
    }
    cout << anss; // 输出最大停靠航班数量
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-08-07 18:01:00
 * 最后修改: 2025-10-07 14:38:04
 * 文件描述:  用到优先队列，45分
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

struct airTime {
    int b,e; // 到达离开时间
};
// 比较函数，用于按起飞时间排序
bool compare(airTime a, airTime b) {
    return a.b < b.b;
}

// 计算可以使用指定数量登机口的最大航班数
int countFlights(vector<airTime>& flights, int gates) {
    if (gates == 0) return 0; // 如果没有登机口，则无法处理任何航班
    priority_queue<int, vector<int>, greater<int>> pq;// 定义一个优先队列，基于离开时间构建最小堆
    int ans = 0; // 记录能够处理的航班数
    // 遍历所有航班
    for (const auto& flight : flights) {
         if (pq.size() < gates) {          // 如果当前使用的登机口数量小于可用登机口数量，则直接分配一个新的登机口
            pq.push(flight.e);          // 将当前航班加入优先队列
            ans++;                      // 计数器加一
        } else if (flight.b > pq.top()) {// 否则，检查当前航班能否使用最早空闲的登机口
            pq.pop();                    // 移除最早空闲的登机口（已经降落的航班）
            pq.push(flight.e);        // 分配登机口给当前航班
            ans++;                    // 计数器加一
        }
    }
    return ans; // 返回能够处理的最大航班数
}

int main() {
    int n, dom, inte;
    cin >> n >> dom >> inte;
    
    vector<airTime> Dom(dom);
    vector<airTime> Inte(inte);
    
    for (int i = 0; i < dom; ++i)  cin >> Dom[i].b >> Dom[i].e;
    for (int i = 0; i < inte; ++i) cin >> Inte[i].b >> Inte[i].e;
    
    sort(Dom.begin(), Dom.end(), compare);
    sort(Inte.begin(), Inte.end(), compare);
    
    int anss = 0; // total number of flights
    for (int i = 0; i <= n; ++i) { // n+1 combinations
        int ansd = countFlights(Dom, i);
        int ansi = countFlights(Inte, n - i);
        anss = max(anss, ansd + ansi);
    }
    cout << anss;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

/**************************************************************** 
 * Description: 优先队列+前缀和 100分
 * Author: Alex Li
 * Date: 2024-08-04 18:06:43
 * LastEditTime: 2024-08-06 17:50:10
****************************************************************/

//核心算法，不管有几个廊桥，某第i个廊桥能停靠的数量是定值！！！有了这个结论才能用前缀和
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int m[2],n;// m[0] 表示国内航班数，m[1] 表示国际航班数，n 表示廊桥数
// 定义航班结构体
struct plane{
    int l,r;   // l 表示航班到达时间，r 表示航班离开时间
}a[2][100000]; // a[0] 表示国内航班，a[1] 表示国际航班

// ans[0][i] 表示使用 i 个廊桥时可以停靠的国内航班数量，
// ans[1][i] 表示使用 i 个廊桥时可以停靠的国际航班数量.
int ans[2][100001];

// 比较函数，用于按到达时间排序
bool mp(plane a, plane b){
    return a.l<b.l;
}
// 计算每个廊桥数量下可以停靠的航班数
void js(int bh){
    // 小顶堆，按起飞时间排序，存储当前在廊桥上的航班,
    //第一个元素 (pair.first) 表示航班的离开时间，第二个元素 (pair.second) 表示廊桥的编号。
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> smwy;
    // 小顶堆，存储空闲的廊桥编号
    priority_queue<int,vector<int>,greater<int>> ytemp;
    //// 初始化廊桥堆
    for(int i=1;i<=n;i++) ytemp.push(i);
    // 遍历所有航班,m[0]是国内，m[1]是国外
    for(int i=1;i<=m[bh];i++){ 
        // 将所有已经起飞的航班从廊桥堆中移除，并将廊桥编号放回空闲廊桥堆
        while(!smwy.empty()&&a[bh][i].l>=smwy.top().first){ 
            ytemp.push(smwy.top().second);
            smwy.pop();
        }
        // 如果没有空闲廊桥，则继续
        if(ytemp.empty())continue;
        int tmp=ytemp.top();// 取出一个空闲廊桥
        ans[bh][tmp]++;// 对应廊桥的航班数加1
        smwy.push(make_pair(a[bh][i].r,tmp));// 将当前航班放入廊桥堆，使用pair表示：{离开时间, 廊桥编号}
        ytemp.pop(); // 移除已使用的廊桥
       
    }
    // 计算前缀和，累积每个廊桥数量下的航班数
    for(int i=1;i<=n;i++)ans[bh][i]+=ans[bh][i-1];
}

int main(){
    cin>>n>>m[0]>>m[1];// 读取廊桥数、国内航班数和国际航班数
    // 读取国内航班信息
    for(int i=1;i<=m[0];i++)cin>>a[0][i].l>>a[0][i].r;
    // 读取国际航班信息
    for(int i=1;i<=m[1];i++)cin>>a[1][i].l>>a[1][i].r;
    // 对国内航班按到达时间排序
    sort(&a[0][0],&a[0][m[0]+1],mp); //区间是左闭右开，a[i]从i=1开始，所以+1
    // 对国际航班按到达时间排序
    sort(&a[1][0],&a[1][m[1]+1],mp);

    js(0);// 计算国内航班的前缀和
    js(1);// 计算国际航班的前缀和
    int mx=-1;
    for(int i=0;i<=n;i++)mx=max(mx,ans[0][i]+ans[1][n-i]);
    cout<<mx<<endl;
    return 0;

}