学步园

代码来源:

http://hi.baidu.com/chingfantsou/item/fb84b21438ac14e55f53b194

#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int p[10001],d[10001];
int md;
int ans;
int h[10001];
struct pro
{
    int p,d;
}pd[10001];
bool cmp(pro a,pro b) {return (a.p>b.p);}
inline int find(int x)
{//并查集查找 递归的路径压缩
    if (h[x]==x) return x;
    h[x]=find(h[x]);
    return h[x];
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        ans=0;
        md=-1;//记录最大截止时间
        for (int i=1;i<=n;i++)
        {
            scanf("%d %d",&pd[i].p,&pd[i].d);
            if (md<pd[i].d) md=pd[i].d;
        }
        sort(pd+1,pd+n+1,cmp);//完全按价值从大到小排序,不考虑时间
        for (int i=0;i<=md;i++) h[i]=i;//初始化并查集
        //注意下标是时间,与商品无关
//h[i]表示第i个单位时间内向前最近[保证尽量迟]是哪一个单位时间有空余
        for (int i=1;i<=n;i++)
            if (find(pd[i].d))
            {//按物品的价值从大到小查找,如果当前物品可卖,则选择
                ans+=pd[i].p;
            //h[pd[i].d]为当前物品卖出的时间(尽量迟)
            //此时间已经被当前商品占据,则对于被占据的时间h[pd[i].d],
            //它向前最近是h[pd[i].d]-1有空余.(X!)
            //就像dp,find的时候不是找这一个数,而是找最前面的根节点.
            //所以这句话的意思是卖出i商品的时间h[pd[i].d]前的最近空余时间
            //就等于h[pd[i].d]-1时间前的最近空余时间(所以说不用担心h[pd[i].d]-1处是否被占用)
                h[h[pd[i].d]]=h[pd[i].d]-1;
            }
    //并查集的作用主要是将时间向前推进.
    //以某个时间为上界,它们只要自己被占据,就必须向前推进
    //而只要和更向前的连通,就都取最前的值.
    //由此可知并查集主要是刻画了连通的性质!
        printf("%d\n",ans);
    }
    return 0;
}