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