CF496E Distributing Parts

首先将曲目和演奏家的范围按照右端点排序.

从左往右扫一遍,只需要对于当前的那个演奏家,将右端点小于它的曲目加入\(set\)中,然后策略肯定是能选就选,并且演奏左端点离他最近的那个曲目,这些都很好用\(set\)维护.

#pragma GCC optimize("Ofast,inline", 3)
#include<bits/stdc++.h>
#define il inline
#define rg register
#define gi read<int>
#define pii pair<int, int>
using namespace std;
const int O = 1e5 + 10;
template<class TT>
il TT read() {
    TT o = 0, fl = 1; char ch = getchar();
    while (!isdigit(ch) && ch != '-') ch = getchar();
    if (ch == '-') fl = -1, ch = getchar();
    while (isdigit(ch)) o = o * 10 + ch - '0', ch = getchar();
    return fl * o;
}
struct Data {
    int l, r, id, k;
    il bool operator < (Data & rhs) const {
        return r < rhs.r;
    }
}a[O], b[O];
int n, m, ans[O], pos = 1;
set<pii >s;
set<pii >::iterator it;
int main() {
    n = gi(); for (int i = 1; i <= n; ++i) a[i] = (Data){gi(), gi(), i};
    m = gi(); for (int i = 1; i <= m; ++i) b[i] = (Data){gi(), gi(), i, gi()};
    sort(a + 1, a + n + 1); sort(b + 1, b + m + 1);
    for (int i = 1; i <= m; ++i) {
        while (b[i].r >= a[pos].r && pos <= n)
            s.insert(pii(a[pos].l, pos)), ++pos;
        while (b[i].k--) {
            it = s.lower_bound(pii(b[i].l, 0));
            if (it == s.end()) break;
            ans[a[it->second].id] = b[i].id;
            s.erase(it);
        }
    }
    for (int i = 1; i <= n; ++i)
        if (!ans[i]) return puts("NO") & 0;
    puts("YES");
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    return 0;
}

CF496E Distributing Parts

原文：https://www.cnblogs.com/lylyl/p/11823389.html