求助 CSP 第一题,WA 65pts
查看原帖
求助 CSP 第一题,WA 65pts
574944
Micnation_AFO楼主2022/3/23 14:26

rt,按第一篇题解思路写的

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

#define int long long
#define pii pair<int, int>
#define maxn 100005
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 + m1 + 1, cmp);
    get_sum(in, m1, sum1), get_sum(out, m2, sum2);
    for (int i = 1; i <= n; i++) ans = max(ans, sum1[i] + sum2[n - i]);
    cout << ans << endl;
    return 0;
}

2022/3/23 14:26
加载中...