[牛客每日一题] 2020-03-24

Gate: https://ac.nowcoder.com/acm/contest/1080/C

题目大意

给你个物品，每个物品有价值，限制表示最多选择多少个物品（要求最终选出来的数量满足所有选出来物品带有的限制）

思路

枚举选择多少个物品，显然所有不低于此限制的物品均能选择，则使用一个优先队列储存当前选择的物品，先加入符合限制的，然后在删除容量的最小的部分即可。
简单贪心。

代码

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 100010;
const ll mod = 1000000007LL;

struct Node {
    int v, s;
} w[N];

inline bool cmp(Node a, Node b)
{
    return a.s > b.s;
}

priority_queue< int, vector<int>, greater<int> > q;

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &w[i].v, &w[i].s);
    }
    sort(w + 1, w + n + 1, cmp);
    int pos = 1, cnt = n;
    ll sum = 0, ans = 0;
    while (cnt > 0) {
        while (w[pos].s == cnt && pos <= n) {
            q.push(w[pos].v);
            sum += w[pos].v;
            ++pos;
        }
        while (q.size() > cnt) {
            sum -= q.top();
            q.pop();
        }
        ans = max(ans, sum);
        --cnt;
    }
    printf("%lld\n", ans);
    return 0;
}