求助 CSP-S 2021 T1 简化版,简单贪心 WA 10pts
查看原帖
求助 CSP-S 2021 T1 简化版,简单贪心 WA 10pts
724958
lixuanyan楼主2022/5/14 17:02
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define maxn 500005
struct cow { int l, r; } t[maxn];
struct node { int time, id; };
int n, sum;
int ans[maxn];
priority_queue<node> q;

bool cmp(cow a, cow b) {
    return a.l < b.l;
}
bool operator<(const node &a, const node &b) {
    return a.time > b.time;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> t[i].l >> t[i].r;
    sort(t + 1, t + 1 + n, cmp);
    ans[1] = 1, sum = 1; q.push((node){t[1].r, 1});
    for (int i = 2; i <= n; i++) {
        if (q.top().time <= t[i].l) {
            int id = q.top().id;
            ans[i] = id; q.pop();
            q.push((node){t[i].r, id});
        }
        else q.push((node){t[i].r, ++sum}), ans[i] = sum;
    }
    cout << sum << endl;
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;
    return 0;
}

另外这题真的有蓝吗?为什么 airport 才绿?

2022/5/14 17:02
加载中...