Solution

由题目可知要求一个集合，使集合大小满足元素的限制且元素之和最大。

一个显然的贪心思想：在满足条件的前提下使得和最大。要求和最大，就可以使用堆来维护。

因此，可以先按 从大到小排序，维护一个小根堆，每插入新元素之前，将堆的大小调整至符合条件。再实时维护一个集合内元素的最大值即可。

时间复杂度：

最后，给大家推荐一道类似的题目：Supermarket

也是维护一个小根堆进行贪心。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+10;
struct node{
    int v;
    int s;
}a[maxn],heap[maxn];
int n,tot;
ll ans,sum;
bool cmp(node x,node y){
    return x.s>y.s;
}
void up(int x){
    while(x>1){
        if(heap[x>>1].v>heap[x].v)
            swap(heap[x>>1],heap[x]);
        else
            break;
        x>>=1;
    }
}
void down(int x){
    int y=x<<1;
    while(y<=tot){
        if(y<n&&heap[y+1].v<heap[y].v)
            y++;
        if(heap[y].v<heap[x].v)
            swap(heap[x],heap[y]);
        else
            break;
        x=y;
        y=x<<1;
    }
}
void Insert(node p){
    heap[++tot]=p;
    up(tot);
}
void Extract(){
    heap[1]=heap[tot--];
    down(1);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].v>>a[i].s;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        while(tot>=a[i].s){
            sum-=heap[1].v;
            Extract();
        }
        Insert(a[i]);
        sum+=a[i].v;
        ans=max(ans,sum);
    }
    cout<<ans;
    return 0;
}