pku1456 Supermarket

#include<stdio.h>
#include<algorithm>

const int MAX=10005;

struct Node
{
    int p,d;
};
Node node[MAX];
int pre[MAX];

int find(int x)    //返回1…x天区间中最后一个可用天的编号，若没有可用则返回-1

{
    if(x<=0) return -1;  //不存在可用天
    if(pre[x]==x)   //存在最接近期限的可用天
    {
        pre[x]--;
        return pre[x];    
    }
    pre[x]=find(pre[x]);  //这段被占据的区间中每一天都指向最近的可用天
    return pre[x];
}

int cmp(const void *a,const void *b)
{
    return (*(Node*)b).p-(*(Node*)a).p;
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int max=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&node[i].p,&node[i].d);
            if(node[i].d>max) max=node[i].d;
        }
        for(int i=0;i<=max;i++) pre[i]=i;        
        qsort(node,n,sizeof(Node),cmp);
        int sum=0;
        for(int i=0;i<n;i++) if(find(node[i].d)!=-1) sum+=node[i].p;
        printf("%d\n",sum);
    }
    return 0;
}