我不知道这个解法是不是正确的反正AC了
时间复杂度也不是很清楚
大体思路是这样的:
其实就是求出所有的
分配给国内或国际机场x(0≤x≤n)个廊桥可以停靠廊桥的飞机数量
求法就是
先按到达时间排序
分配了x−1个廊桥可以停靠的飞机数量再加上新加的一个廊桥带来的贡献
为了优化时间我声明了一个数组维护每一架飞机离开后最早的来停靠的飞机的飞机编号(二分求的)
具体看代码吧写不清楚了
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100015;
inline int read() {
int s = 0, f = 1;
char ch = getchar();
while (ch < 48 || ch > 57) {
if (ch == 45) {
f = -1;
}
ch = getchar();
}
while (ch > 47 && ch < 58) {
s = (s << 3) + (s << 1) + ch - 48;
ch = getchar();
}
return s * f;
}
struct node {
int l, r;
bool operator < (const node &rhs) const {
return l < rhs.l;
}
} List1[maxn], List2[maxn];
int n, m1, m2, ans, id1[maxn], id2[maxn], ans1[maxn], ans2[maxn];
bool vis1[maxn], vis2[maxn];
int BS(int l, int r, int val, bool flag) {
if (flag) {
if (List2[m2].l <= val) {
return 0;
}
}
else {
if (List1[m1].l <= val) {
return 0;
}
}
int mid;
while (l < r) {
mid = (l + r) >> 1;
if (flag) {
if (List2[mid].l > val) {
r = mid;
}
else {
l = mid + 1;
}
}
else {
if (List1[mid].l > val) {
r = mid;
}
else {
l = mid + 1;
}
}
}
return l;
}
int main(void) {
n = read();
m1 = read();
m2 = read();
for (register int i = 1; i <= m1; i++) {
List1[i].l = read();
List1[i].r = read();
}
for (register int i = 1; i <= m2; i++) {
List2[i].l = read();
List2[i].r = read();
}
sort(List1 + 1, List1 + m1 + 1);
sort(List2 + 1, List2 + m2 + 1);
for (register int i = 1; i < m1; i++) {
id1[i] = BS(i + 1, m1, List1[i].r, 0);
}
for (register int i = 1; i < m2; i++) {
id2[i] = BS(i + 1, m2, List2[i].r, 1);
}
int pos;
for (register int i = 1; i <= n; i++) {
ans1[i] = ans1[i - 1];
if (ans1[i] < m1) {
pos = 1;
while (pos) {
while (vis1[pos]) {
pos++;
}
if (pos <= m1) {
vis1[pos] = 1;
ans1[i]++;
}
pos = id1[pos];
}
}
ans2[i] = ans2[i - 1];
if (ans2[i] < m2) {
pos = 1;
while (pos) {
while (vis2[pos]) {
pos++;
}
if (pos <= m2) {
vis2[pos] = 1;
ans2[i]++;
}
pos = id2[pos];
}
}
}
for (register int i = 0; i <= n; i++) {
ans = max(ans, ans1[i] + ans2[n - i]);
}
printf("%d", ans);
return 0;
}