solution

考虑枚举所选择的数中最小的。然后就是要在所有的数中找到最大的个。

所以先按照s从大到小排序,然后再维护一个小根堆,存放当前的答案。每当堆的大小大于当前的s时,就弹出元素。最后找到一个最大的答案即可。

code

/*
* @Author: wxyww
* @Date: 2020-05-05 20:52:24
* @Last Modified time: 2020-05-05 21:01:26
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 200010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,s;
}a[N];
bool cmp(const node &A,const node &B) {
    return A.s > B.s;
}

priority_queue<int,vector<int>,greater<int> >q;
int main() {
    int n = read();
    for(int i = 1;i <= n;++i) {
        a[i].v = read();a[i].s = read();
    }
    sort(a + 1,a + n + 1,cmp);
    ll ans = 0,anss = 0;

    for(int i = 1;i <= n;++i) {
        q.push(a[i].v);
        ans += a[i].v;
        while(q.size() > a[i].s) {
            ans -= q.top();q.pop();
        }
        anss = max(ans,anss);
    }
    cout<<anss<<endl;
    return 0;
}