Supermarket POJ - 1456 贪心+并查集

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5;
struct edge{
    int w;
    int deadline;
}e[N];
bool cmp(edge a,edge b)
{
    return a.w>b.w;
}
int f[N];
int find(int x)
{
    if(f[x]!=x)
        f[x]=find(f[x]);
    return f[x];
}
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=1;i<=N;i++)
            f[i]=i;
        for(int i=0;i<n;i++)
            cin>>e[i].w>>e[i].deadline;
        sort(e,e+n,cmp);
        int res=0;
        for(int i=0;i<n;i++)
        {
            //   刚开始占用了第x天  p[x]=x-1
            //  占用第x-1天   p[x-1]=x-2
            //此时再占用x   p[x]=x-1
            //p[x-1]=x-2
            //p[x-2]=x-2  占用 
            int x=find(e[i].deadline);
            if(x>0)
            {
                //该商品已经用了这一天，所以其他商品要用的话只能提前，所以-1
                f[x]=x-1;
                res+=e[i].w;
            }
        }
        cout<<res<<endl;
    }
}