超市

AcWing-145-超市

分析

见《进阶指南》第83页。

实现

#include <iostream>
#include <queue>
#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];
priority_queue<node> pq;

bool cmp (const node& a, const node& b) {
    return a.d < b.d;
}

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

        sort(a + 1, a + n + 1, cmp); // 按保质期由小到大排序
        for (int i = 1; i <= n; ++ i) {
            node cur = a[i];
            if (cur.d == pq.size()) { // 满员
                if (pq.top().p < cur.p) {
                    pq.pop();
                    pq.push(cur); // 置换
                }
            }
            if (cur.d > pq.size())
                pq.push(cur);
        }
        int res = 0;
        while (!pq.empty()) {
            res += pq.top().p;
            pq.pop();
        }
        cout << res << endl;
    }
    return 0;
}