思路:

算是比较有意思的贪心^-^
其实乍看就是简单01背包问题,由于我太弱没想到怎么优化复杂度。
于是,换了贪心思路。


考虑一个简单问题,如果现在给定最多取K人,那么怎样最优取呢?
显然找出n个人中s[]大于等于K的人,记为S。
那我们只需要在S集合中找前K大的v值,并对其求和


敲黑板:
最暴力的方法就是,然而这道题给的人数规模为n,也是表明K最多有n种,这样暴力跑下来复杂度还是


如何优化复杂度呢?
我们把n个人的s进行从高到低排序,若,记取值集合为S1,取值集合为S2,
S2肯定包含S1中部分元素,这就表明在求解S2时有些元素根本不需要枚举,直接从S1中获得了,这就是优化的出发点。


用SUM记为当前优先队列的元素和,NUM记为当前优先队列的元素个数
优先队列维护v值单调不减


当我们枚举到第i个人时,我们需要把K置为该人的s,然后把这个人加到集合,更新SUM与NUM;
然后不断POP优先队列,直到NUM<=K,不断更新SUM;


总复杂度:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 +10;
struct node{
    ll v;
    int s;
}a[maxn];
int n;
bool cmp(node b, node c){
    if(b.s == c.s) return b.v < c.v;
    else return b.s < c.s;
}
void solve(){
    ll ans = -1;
    priority_queue<ll, vector<ll>, greater<ll>> que;
    ll sum = 0;///队列元素和
    int num = 0;///队列元素个数
    int max_size;
    for(int i = n; i >= 1; i--){
        max_size = a[i].s; num++; sum += a[i].v; que.push(a[i].v);
        while(num && num > max_size){sum -= que.top(); que.pop(); num--;}
        ans = max(ans, sum);
    }
    printf("%lld\n", ans);
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lld%d", &a[i].v, &a[i].s);
    }
    sort(a + 1, a + n + 1, cmp);
    solve();
    return 0;
}