POJ - 1456 Supermarket

題意：買賣N件東西，每件東西都有個截止時間，在截止時間之前買都可以，而每個單位時間只能買一件。問最大獲利。

思路：顯然貪心是這道題的方法，如果在商品的最後的日期能買的話，就買，否則看看它之前一天的時間能不能買，依次類推，怎麼標記我們能買的日子呢，並查集解決，初始化都是-1，如果被占用了，那麼就找前一個節點也就是昨天，直到找到沒被占用的日子

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 10010;

struct node{
    int p,d;
}arr[MAXN];
int f[MAXN],n;

bool cmp(node a,node b){
    return a.p > b.p;
}

int find(int x){
    if (f[x] == -1)
        return x;
    return f[x] = find(f[x]);
}


int main(){
    while (scanf("%d",&n) != EOF){
        memset(f,-1,sizeof(f));
        for (int i = 0; i < n; i++)
            scanf("%d%d",&arr[i].p,&arr[i].d);
        sort(arr,arr+n,cmp);
        int ans = 0;
        for (int i = 0; i < n; i++){
            int t = find(arr[i].d);
            if (t > 0){
                ans += arr[i].p;
                f[t] = t-1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}