CSP2021 S2参考解析

#include<bits/stdc++.h>
#include<queue>
using namespace std;
const int N=1e5+10;
struct T {
    int begin,end;
} a[N], b[N];
int ans1[N], ans2[N], vis[N];
bool cmp(T a, T b) {
    if(a.begin!=b.begin) return a.begin<b.begin;
    return a.end<b.end;
}

//在 m个廊桥 n个飞机最多可以停靠在廊桥的数量
int fun1(T arr[], int n, int m) {
    if(m==0) return 0; //特判
    int ans=0;
    priority_queue<int, vector<int>, greater<int> > prq;//小顶推
    for(int i=1; i<=n; i++) {
        if(prq.size()<m) {
            prq.push(arr[i].end);
            ans++;
        } else {
            int first_end_time = prq.top();
            if(arr[i].begin >= first_end_time) {
                prq.pop();
                prq.push(arr[i].end);
                ans++;
            }
        }
    }
    return ans;
}

void print(T arr[], int n) {
    for(int i=1; i<=n; i++) printf("%d %d\n", arr[i].begin, arr[i].end);
    printf("\n");
}

// 方法1：啥也不会，只能硬刚，模拟一遍过程，有 40分
// 枚举分配给国内航班与国外航班的廊桥数量
int main1() {
    freopen("airport.in", "r", stdin);
    freopen("airport.out", "w", stdout);

    int n,m1,m2; scanf("%d%d%d", &n, &m1, &m2);
    for(int i=1; i<=m1; i++) cin>>a[i].begin>>a[i].end;
    for(int i=1; i<=m2; i++) cin>>b[i].begin>>b[i].end;
    sort(a+1, a+1+m1, cmp);
    sort(b+1, b+1+m2, cmp);

    int max_ans=0;
    for(int x=0; x<=n; x++) {
        int y=n-x;// x 是分配给国内机场的数量， y 是分配给国际机场的数量
        int ans1=fun1(a, m1, x);
        int ans2=fun1(b, m2, y);
        max_ans = max(max_ans, ans1+ans2);
    }
    printf("%d\n", max_ans);

    fclose(stdin);  fclose(stdout);
    return 0;
}

// ans[i] 前 i条廊桥最多可停放的飞机数量,共 n个廊桥，m架飞机
// 国内和国外飞机停靠是互不影响且相同的，所以考虑一个即可
void fun2(T arr[], int m, int n, int ans[]){
//    pair<int, int> -> 第一个离场飞机时间, 廊桥 id, priority_queue对pair的排序规则为：first,second
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > >prq1; //现在飞机廊桥停靠情况
    priority_queue<int, vector<int>, greater<int> >prq2;//堆顶存放最先廊桥 id
    for(int i=1; i<=n; i++) prq2.push(i);
    for(int i=1; i<=m; i++){
        while(!prq1.empty() && arr[i].begin>=prq1.top().first){
            prq2.push(prq1.top().second); prq1.pop();
        }
        if(prq2.empty()) continue;
        int id=prq2.top(); prq2.pop();
        prq1.push(make_pair(arr[i].end, id)); ans[id]++;
    }
    for(int i=1; i<=n; i++) ans[i]+=ans[i-1];
}

// 方法2：前缀和
int main() {
//    freopen("airport.in", "r", stdin);
//    freopen("airport.out", "w", stdout);

    int n,m1,m2; scanf("%d%d%d", &n, &m1, &m2);
    for(int i=1; i<=m1; i++) cin>>a[i].begin>>a[i].end;
    for(int i=1; i<=m2; i++) cin>>b[i].begin>>b[i].end;
    sort(a+1, a+1+m1, cmp);
    sort(b+1, b+1+m2, cmp);

    fun2(a, m1, n, ans1);
    fun2(b, m2, n, ans2);
    int max_ans=0;
    for(int i=0; i<=n; i++){
        max_ans=max(max_ans, ans1[i]+ans2[n-i]);
    }
    printf("%d\n", max_ans);

    fclose(stdin); fclose(stdout);
    return 0;
}