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;
}

总结:

首先进行预处理，让获利大的产品先卖，并尽量占据最接近期限的可用天。每一天i指向最接近i的可用天，
因而初始pre[i]=i,当位于接近期限i的可用天被占用后pre[i]--,即指向下一个能被期限i可用的天的编号,当下
一个可用天是另一个期限时，就要考虑合并这两个期限的可用天，即让这两个期限分享最接近这两个期限
的可用天，依次类推，直至没有空闲天可用。