题目大意

个物品，第 个有价值 ，选了第 个就要求选取物品总个数不超过 ，求最大价值和。

题解

物品按照 从大到小排序，然后枚举 ，用堆保留价值最大的 个物品即可。时间复杂度 。

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n;
pair<int, int> pp[100005];
priority_queue<int, vector<int>, greater<int> > pq;
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        pp[i].second = read(), pp[i].first = -read();
    sort(pp + 1, pp + n + 1);
}
void solve(){
    ll ans = 0, sm = 0;
    for (int cur = 1; ; ){
        while (cur <= n){
            if (pq.size() + 1 > -pp[cur].first)   
                break;
            pq.push(pp[cur].second);
            sm += 1ll * pp[cur].second;
            ++cur;
        }
        ans = max(ans, sm);
        if (cur <= n){
            while (!pq.empty() && pq.size() + 1 > -pp[cur].first)
                sm -= pq.top(), pq.pop();
        }else break;
    }
    printf("%lld\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}