我真的是无语了,初赛没过也就算了,这第一题都想不明白
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int M = 1e5 + 10;
int n, m1, m2;
int b1[M], b2[M];
struct node{
int num, s, e; // num表示如果可以会停在第几个廊桥
}temp[M];
bool cmp(node i, node j) {
return i.s < j.s;
}
struct tmp{
bool operator() (node a, node b) {
return a.e > b.e; // 小顶堆
}
};
void debug(int k[]) {
for (int i = 0;i <= 50;i ++)
cout << k[i] << ' ';
cout << endl;
}
void solve(int m, int b[]) {
memset(temp, 0, sizeof temp);
for (int i = 1;i <= m;i ++) {
cin >> temp[i].s >> temp[i].e;
}
sort(temp + 1, temp + m + 1, cmp);
priority_queue<node, vector<node>, tmp> q;
temp[1].num = 1;
q.push(temp[1]);
int idx = 2;
int mx = 1;
while (idx <= m) { // 模拟飞机进出机场的情况
if (q.top().e < temp[idx].s) {
temp[idx].num = q.top().num;
// 若有飞机可以走了,就停在要走的廊桥中
q.pop();
q.push(temp[idx]);
}
else {
mx ++;
temp[idx].num = mx;
q.push(temp[idx]);
// 没有空位,另外开拓廊桥
}
idx ++;
}
for (int i = 1;i <= n + 1;i ++) {
b[i] = 0;
}
for (int i = 1;i <= m;i ++) {
b[temp[i].num] ++;
}
for (int i = 1;i <= n;i ++) {
b[i] += b[i - 1];
// 前缀和求一种机场里若有 i 个廊桥就会有 b[i] 个飞机可以停在廊桥里
}
}
int main() {
cin >> n >> m1 >> m2;
solve(m1, b1);
solve(m2, b2);
// debug(b1);debug(b2);
int i = 0, ans = 0;
while (n - i > 0) {
ans = max(ans, b1[i] + b2[n - i]); // 取最大值
i ++;
}
cout << ans << endl;
return 0;
}
想了半天了,虽然能过1,2样例,但数据大的样例3都过不去,数据太大也不好手算模拟。