超市

AcWing-145-超市

分析

见《进阶指南》第195页。

实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;
struct node {
    int p, d;
    bool operator < (const node& o) const {
        return p > o.p;
    }
};
node a[N];
int f[N];

int find (int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}

int main () {
    int n;
    while (cin >> n) {
        for (int i = 0; i <= 10000; ++ i) f[i] = i;
        for (int i = 1; i <= n; ++ i) cin >> a[i].p >> a[i].d;

        sort(a + 1, a + n + 1);
        int res = 0;
        for (int i = 1; i <= n; ++ i) {
            int r = find(a[i].d);
            if (r == 0) continue;
            // 第 r 天卖出
            res += a[i].p;
            f[r] = find(r - 1);
        }
        cout << res << endl;
    }
    return 0;
}