考虑将出售每个物品尽量外后安排。这样当一个商品不能安排的时候看能不能替换掉它能够出售的时间中盈利最小的商品。
因此可以将物品排序,这样只用考虑能否让每个物品出售。
为了找到第一个空闲时间,又因为已经安排的时间不会改变,所以用并查集将已经安排了出售的时间段缩起来。
Code
/**
* poj
* Problem#1456
* Accepted
* Time: 47ms
* Memory: 768k
*/
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
typedef bool boolean; typedef class Product {
public:
int profit;
int deadline; Product() { } boolean operator < (Product b) const {
return profit > b.profit;
}
}Product; const int N = 1e4 + ; int n, res;
int pre[N];
Product *ps;
boolean vis[N]; inline boolean init() {
if (scanf("%d", &n) == EOF)
return false;
res = ;
ps = new Product[(n + )];
for (int i = ; i <= n; i++)
scanf("%d%d", &ps[i].profit, &ps[i].deadline);
return true;
} int findPre(int p) {
if (!p) return ;
if (!vis[p]) {
vis[p] = true;
return p;
}
return pre[p] = findPre(pre[p]);
} inline void solve() {
sort(ps + , ps + n + );
memset(vis, false, sizeof(vis));
for (int i = ; i <= ; i++)
pre[i] = i - ;
for (int i = ; i <= n; i++) {
int p = findPre(ps[i].deadline);
if (p)
res += ps[i].profit;
}
printf("%d\n", res);
delete[] ps;
} int main() {
while (init())
solve();
return ;
}