复赛-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
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

/**************************************************************** 
 * Description: 2021年CSP-S复赛，模拟算法，30分
 * Author: Alex Li
 * Date: 2024-08-04 18:04:32
 * LastEditTime: 2024-08-06 17:20:34
****************************************************************/
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

// 定义航班结构体，包含起飞时间和降落时间
struct airTime{
    int b; // 航班开始时间
    int e; // 航班结束时间
} temp;

// 比较函数，用于按开始时间排序航班
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> airTimeDom; // 存储国内航班信息
    vector<airTime> airTimeinte; // 存储国际航班信息
    
    // 读取所有国内航班信息
    for (int i = 0; i < dom; i++) {
        cin >> temp.b >> temp.e; // 读取航班的开始时间和结束时间
        airTimeDom.push_back(temp); // 添加到国内航班列表
    }
    
    // 按航班开始时间对国内航班排序
    sort(airTimeDom.begin(), airTimeDom.end(), compare);
    
    // 读取所有国际航班信息
    for (int i = 0; i < inte; i++) {
        cin >> temp.b >> temp.e; // 读取航班的开始时间和结束时间
        airTimeinte.push_back(temp); // 添加到国际航班列表
    }
    
    // 按航班开始时间对国际航班排序
    sort(airTimeinte.begin(), airTimeinte.end(), compare);
    
    int anss = 0; // 最终能停靠廊桥的最大航班数量
    
    // 遍历所有可能的廊桥分配方案
    for (int i = 0; i <= n; i++) {
        int ansd = 0; // 国内航班计数
        
        // 如果分配的廊桥数大于0
        if (i != 0) {
            int domline[i]; // 存储当前使用的廊桥分配情况
            bool sp = false; // 用于标记是否已分配完所有廊桥
            memset(domline, -1, sizeof(domline)); // 初始化廊桥分配数组为-1
            
            // 遍历所有国内航班
            for (int j = 0; j < dom; j++) {
                if (!sp) { // 如果还未分配完所有廊桥
                    for (int k = 0; k < i; k++) {
                        if (domline[k] == -1) { // 如果当前廊桥空闲
                            domline[k] = j; // 分配当前航班到该廊桥
                            ansd++; // 国内航班计数增加
                            if (ansd == i) { // 如果已分配完所有廊桥
                                sp = true; // 标记分配完成
                                break;
                            }
                            j++;
                        }
                    }
                } else {
                    for (int k = 0; k < i; k++) {
                        // 如果当前航班可以使用该廊桥
                        if (airTimeDom[j].b > airTimeDom[domline[k]].e) { 
                            domline[k] = j; // 更新廊桥分配
                            ansd++; // 国内航班计数增加
                            break;
                        }
                    }
                }
            }
        }
        
        int x = n - i; // 剩余廊桥数用于国际航班
        int ansi = 0; // 国际航班计数
        
        // 如果剩余廊桥数大于0
        if (x != 0) {
            int inteline[x]; // 存储当前使用的廊桥分配情况
            bool sp = false; // 用于标记是否已分配完所有廊桥
            memset(inteline, -1, sizeof(inteline)); // 初始化廊桥分配数组为-1
            
            // 遍历所有国际航班
            for (int j = 0; j < inte; j++) {
                if (!sp) { // 如果还未分配完所有廊桥
                    for (int k = 0; k < x; k++) {
                        if (inteline[k] == -1) { // 如果当前廊桥空闲
                            inteline[k] = j; // 分配当前航班到该廊桥
                            ansi++; // 国际航班计数增加
                            if (ansi == x) { // 如果已分配完所有廊桥
                                sp = true; // 标记分配完成
                                break;
                            }
                            j++;
                        }
                    }
                } else {
                    for (int k = 0; k < x; k++) {
                        // 如果当前航班可以使用该廊桥
                        if (airTimeinte[j].b > airTimeinte[inteline[k]].e) { 
                            inteline[k] = j; // 更新廊桥分配
                            ansi++; // 国际航班计数增加
                            break;
                        }
                    }
                }
            }
        }
        
        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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

/**************************************************************** 
 * Description: 用到优先队列，45分
 * Author: Alex Li
 * Date: 2024-08-04 18:05:34
 * LastEditTime: 2024-08-06 17:46:50
****************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

struct airTime {
    int b; // 起飞时间
    int e; // 降落时间
};

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

// 定义比较结束时间的仿函数，用于优先队列
struct CompareEndTime {
    bool operator()(const airTime& a, const airTime& b) {
        return a.e > b.e; // 基于降落时间的最小堆
    }
};

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

int main() {
    int n, dom, inte;
    cin >> n >> dom >> inte;
    
    vector<airTime> airTimeDom(dom);
    vector<airTime> airTimeInte(inte);
    
    for (int i = 0; i < dom; ++i) {
        cin >> airTimeDom[i].b >> airTimeDom[i].e;
    }
    
    for (int i = 0; i < inte; ++i) {
        cin >> airTimeInte[i].b >> airTimeInte[i].e;
    }
    
    sort(airTimeDom.begin(), airTimeDom.end(), compare);
    sort(airTimeInte.begin(), airTimeInte.end(), compare);
    
    int anss = 0; // total number of flights
    for (int i = 0; i <= n; ++i) { // n+1 combinations
        int ansd = countFlights(airTimeDom, i);
        int ansi = countFlights(airTimeInte, 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;

}