0w1

POJ 1456 Supermarket ( Greedy + Union Find )

1456 -- Supermarket
很顯然要從最貴的開始放,而且是放到離他期限最近的時間點。我們需要快速查詢 lastDay[ i ],代表第 i天( 含 )之前最晚的還沒有賣東西的時間,又因為這件事可以指來指去 i.e. lastDay[ 5 ] = 3 AND lastDay[ 3 ] = 1 -> lastDay[ 5 ] = 1,因此我們可以考慮用並查集維護。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 4;

struct item{
    int val, dl;
    bool operator < (const item &b) const{
        return val > b.val;
    }
}P[MAXN];

int N, lastDay[MAXN], ans;

void init(){
    ans = 0;
    for(int i = 0; i < MAXN; ++i)
        lastDay[i] = i;
}

int find(int a){
    return lastDay[a] == a ? a : lastDay[a] = find(lastDay[a]);
}

int main(){
    while(~scanf("%d", &N)){
        init();
        for(int i = 0; i < N; ++i)
            scanf("%d %d", &P[i].val, &P[i].dl);
            sort(P, P + N);
        for(int i = 0; i < N; ++i){
            int dl = find(P[i].dl);
            if(lastDay[dl] == 0) continue;
            lastDay[dl] = dl - 1;
            ans += P[i].val;
        }
        printf("%d\n", ans);
    }
    return 0;
}