题目大意

30pts

枚举国内、国外廊桥的个数，对于每一种可能，依次求解国内、外可停留的个数，然后取最大值。这里把国内廊桥和国外廊桥看成两个完全不同的区域，对其分别求解。

令 $sta_i$ 表示第 $i$ 架飞机到达的时间，$fin_i$ 表示第 $i$ 架飞机离开的时间。那么对于每一架飞机停留时，就令 $c_{sta_i}$ 加一，$c_{fin_i}$ 减一，表示在 $sta_i$ 到 $fin_i$ 之间停靠飞机的个数又增加了一个。判断一个时间点的飞机数量，求出 $c$ 数组的前缀和即可。这里可以用树状数组进行优化。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x & (-x))
#define maxn 100005
struct airport {
    int sta, fin;
} in[maxn], out[maxn];
int n, m1, m2;
int ans = 0;
int c[maxn];
int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { f = (ch == '-' ? -1 : f); ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
bool cmp(airport x, airport y) {
    return x.sta < y.sta;
}
void change(int x, int v) {
    for (; x <= maxn; x += lowbit(x)) c[x] += v;
}
int ask(int x) {
    int ans = 0;
    for (; x; x -= lowbit(x)) ans += c[x];
    return ans;
}
int num(int x, int y) {
    memset(c, 0, sizeof(c));
    int sum = 0;
    for (int i = 1; i <= m1; i++) {
        int s = in[i].sta, f = in[i].fin;
        if (ask(s) >= x) continue;
        sum++, change(s, 1), change(f, -1);
    }
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= m2; i++) {
        int s = out[i].sta, f = out[i].fin;
        if (ask(s) >= y) continue;
        sum++, change(s, 1), change(f, -1);
    }
    return sum;
}
signed main() {
    n = read(), m1 = read(), m2 = read();
    for (int i = 1; i <= m1; ++i) cin >> in[i].sta >> in[i].fin;
    for (int i = 1; i <= m2; ++i) cin >> out[i].sta >> out[i].fin;
    sort(in + 1, in + 1 + m1, cmp);
    sort(out + 1, out + 1 + m2, cmp);
    for (int len1 = 0, len2 = n; len1 <= n; ++len1, --len2) {
        int val = num(len1, len2);
        ans = max(val, ans);
    }
    cout << ans << endl;
    return 0;
}

Sol

我们可以先求出把廊桥全部给国内和全部给国外答案分别是多少。注意，一定要先给飞机按照到达时间的先后进行排序（因为题目要求先到的飞机先停，与飞机的离开时间无关）。然后给每一个廊桥编号，即 $1,2\cdots n$，刚开始，这些廊桥都是空闲的。用一个队列保存空闲廊桥的编号，并把这些廊桥都放进去。再用一个队列，保存目前正在停留飞机的信息（离开时间和所停留廊桥的编号）。当一架飞机到达的时候，先将其到达时间与最早离开的飞机的离开时间进行比较，如果比它早，就将其出队，并把它所停留的廊桥加入空廊桥的队列。再与剩下的飞机中的最早离开的飞机进行比较，以此类推。最后把飞机放在最小的廊桥。如果没有闲置的廊桥，就不管这架飞机了。那么问题来了：如何将新到达的飞机与目前机场上最早离开的进行比较？存储目前正在停留的飞机的队列并不一定能保证队头就是最早离开的飞机啊。而且如何把新到达的飞机加入序号最小的廊桥？答案是用优先队列：把上述两个队列全部换为优先队列，并从小到大排列即可。

那么如何统计数量呢？相信很多人都是这样想的：刚才不是已经说了：

最后把飞机放在最小的廊桥。

开个计数器，每次新加入飞机的时候把它加一不就行了吗？

但是，这里我们不这样做。我们用一个数组 sum 进行记数。当一架飞机进入 $i$ 号廊桥时，令 $sum_i$ 加一。这样，如果分配到 $x$ 个廊桥，那么这个区域（国内或国外）能停在廊桥的飞机的数量就是：

理由也很简单：如果分配到 $x$ 个廊桥，那么剩下的 $n - x$ 个廊桥我们就当它是远机位就行了，飞机停留的顺序并不会改变，只不过前 $x$ 号廊桥停的会被计入答案，而剩下的廊桥我们把它看成远机位，因此不计入答案。

说了这么多我想你们也没听懂，毕竟这题用语言还是很难表述的，附上 $\texttt{AC}$ 代码辅以理解：

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define maxn 100005
#define free ccf
struct airport { int x, y; };
int n, m1, m2, ans;
airport in[maxn], out[maxn];
int sum1[maxn], sum2[maxn];

bool cmp(airport a, airport b) {
    return a.x < b.x;
}

void get_sum(airport* a, int m, int* sum) {
    priority_queue< pii, vector<pii>, greater<pii> > stop;
    priority_queue< int, vector<int>, greater<int> > free;
    for (int i = 1; i <= n; i++) free.push(i);
    for (int i = 1; i <= m; i++) {
        while (stop.size() && stop.top().first < a[i].x) 
            free.push(stop.top().second), stop.pop();
        if (free.empty()) continue;
        int next = free.top();
        free.pop();
        pii l = make_pair(a[i].y, next);
        stop.push(l);
        sum[next]++;
    }
    for (int i = 1; i <= n; i++) sum[i] += sum[i - 1];
}

signed main() {
    cin >> n >> m1 >> m2;
    for (int i = 1; i <= m1; ++i) cin >> in[i].x >> in[i].y;
    for (int i = 1; i <= m2; ++i) cin >> out[i].x >> out[i].y;
    sort(in + 1, in + m1 + 1, cmp), sort(out + 1, out + m2 + 1, cmp);
    get_sum(in, m1, sum1), get_sum(out, m2, sum2);
    for (int i = 0; i <= n; i++) ans = max(ans, sum1[i] + sum2[n - i]);
    cout << ans << endl;
    return 0;
}