UVA1316 Supermarket

传送门

Solution

对物品以过期时间（从小到大）为第一关键字，价格（从大到小）为第二关键字进行排序，然后开一个按照物品价值排序的小根堆。

按顺序枚举物品，若当前物品过期时间大于堆的大小，则物品压入堆中。若过期时间等于堆的大小，则将其与堆顶物品比较，取价值大的留在堆中。显然不可能出现物品过期时间小于堆的大小的情况。

最后将堆中物品价值相加即为答案。

Code

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

const int N = 1e4 + 10;

int n, ans;
struct Node {
    int x, y;
    friend bool operator > (const Node &a, const Node &b) {
        return a.x > b.x;
    }
    friend bool operator < (const Node &a, const Node &b) {
        return a.x < b.x;
    }
} a[N];
priority_queue<Node, vector<Node>, greater<Node> > q;

bool cmp(const Node &a, const Node &b) 
{
    if (a.y == b.y)
        return a.x > b.x;
    return a.y < b.y;
}

void solve()
{
    ans = 0;
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].x, &a[i].y);
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        int x = a[i].x, y = a[i].y;
        if (q.size() < y)
            q.push(a[i]);
        else if (q.size() == y) {
            if (q.top().x < x) {
                q.pop();
                q.push(a[i]);
            }
        }
    }
    while (q.size()) {
        ans += q.top().x;
        q.pop();
    }
    printf("%d\n", ans);
}

int main()
{
    while (scanf("%d", &n)) solve();
    return 0;
}