很明显的贪心策略,先按权值排序,从过期时间向前遍历,给后面的权值插入创造更多的可能
遍历的过程用并查集减少时间。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=11000;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
struct node{int d,t;bool operator <(const node a)const{return d>a.d;}}a[N];
int fa[N];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)qr(a[i].d),qr(a[i].t);  
        for(int i=1;i<=10000;i++)fa[i]=i;    
        sort(a+1,a+n+1);int ans=0;
        for(int i=1;i<=n;i++)
        {
            int t=get(a[i].t);
            if(!t)continue;
            ans+=a[i].d;
            fa[t]=t-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}