526互联

P7913 [CSP-S 2021] 廊桥分配

发布时间 2023-09-26 18:07:32作者: RonChen

暴力枚举

枚举国内和国外的廊桥数量配额，再模拟航班停机过程

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100005;
struct Flight {
    int l, r; // l 抵达时刻，r 离开时刻
    bool operator<(const Flight& other) const {
        return l < other.l;
    }
};
Flight a[N], b[N]; // a 国内，b 国际
int t[N]; // 廊桥目前停靠飞机的离开时刻
int solve(Flight f[], int m, int len) {
    for (int i = 1; i <= len; i++) t[i] = 0;
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        int id = 0;
        for (int j = 1; j <= len; j++) 
            if (f[i].l >= t[j]) {
                id = j; break;
            } 
        if (id != 0) {
            t[id] = f[i].r; cnt++;
        }
    }
    return cnt;
}
int main()
{
    int n, m1, m2;
    scanf("%d%d%d", &n, &m1, &m2);
    for (int i = 1; i <= m1; i++) scanf("%d%d", &a[i].l, &a[i].r);
    for (int i = 1; i <= m2; i++) scanf("%d%d", &b[i].l, &b[i].r);
    // 按抵达时间排序
    sort(a + 1, a + m1 + 1); sort(b + 1, b + m2 + 1);
    int ans = 0;
    for (int x = 0; x <= n; x++) {
        // 给国内航班预留 x 个廊桥，国外航班预留 n-x 个
        int y = n - x;
        int cnt1 = solve(a, m1, x);
        int cnt2 = solve(b, m2, y);
        ans = max(ans, cnt1 + cnt2);
    }
    printf("%d\n", ans);
    return 0;
}

正解

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 100005;
struct Flight {
    int arrive, leave;
    bool operator<(const Flight& other) const {
        return arrive < other.arrive;
    }
};
Flight f1[MAXN], f2[MAXN];
int cnt1[MAXN], cnt2[MAXN], sum1[MAXN], sum2[MAXN];
struct Bridge {
    int time, id;
};
struct BridgeCompare {
    bool operator()(const Bridge &lhs, const Bridge &rhs) const {
        return lhs.time > rhs.time;
    }
};
priority_queue<Bridge, vector<Bridge>, BridgeCompare> q1;
priority_queue<int, vector<int>, greater<int>> q2;
void distribute(Flight f[], int cnt[], int m) {
    while (!q1.empty()) q1.pop();
    while (!q2.empty()) q2.pop();
    for (int i = 1; i <= m; i++) {
        while (!q1.empty() && q1.top().time <= f[i].arrive) {
            q2.push(q1.top().id);
            q1.pop();
        } 
        if (q2.empty()) {
            int len = ++cnt[0];
            cnt[len] = 1;
            q1.push({f[i].leave, len});
        } else {
            cnt[q2.top()]++;
            q1.push({f[i].leave, q2.top()});
            q2.pop();
        }
    }
}
int main()
{
    int n, m1, m2;
    scanf("%d%d%d", &n, &m1, &m2);
    for (int i = 1; i <= m1; i++) scanf("%d%d", &f1[i].arrive, &f1[i].leave);
    for (int i = 1; i <= m2; i++) scanf("%d%d", &f2[i].arrive, &f2[i].leave);
    sort(f1 + 1, f1 + m1 + 1);
    sort(f2 + 1, f2 + m2 + 1);
    distribute(f1, cnt1, m1);
    distribute(f2, cnt2, m2);
    for (int i = 1; i <= n; i++) sum1[i] = sum1[i - 1] + cnt1[i];
    for (int i = 1; i <= n; i++) sum2[i] = sum2[i - 1] + cnt2[i];
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = max(ans, sum1[i] + sum2[n - i]);
    }
    printf("%d\n", ans);
    return 0;
}