http://poj.org/problem?id=1456
题意：给你 N 件不同的商品，每件商品最多可以买一次。每件物品对应两个值 pi di
pi 表示物品的价值，di 表示可以买的最迟时间（也就是第一天到第 di 天都可以买这件物品）
规定：每天最多可以买一件物品，问你可以得到的最大价值。
思路【贪心版本】：将物品按照价值从大到小排序
依次枚举每件物品
从可以买的最后一天枚举，看是否可以买
注意：标记天数。
思路【KB的并查集版本】：将物品按照价值从大到小排序
处理的时候选择最后的一个不冲突点。
用并查集实现链表的作用，快速找到不冲突点。
贪心版本
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e4 + 10;
int n;
bool book[maxn];
struct Node {
int p, d;
}node[maxn];
bool cmp(Node a, Node b) {
return a.p > b.p;//按价值排序
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
while (cin >> n) {
memset(book, false, sizeof book);
for (int i = 1; i <= n; ++i)cin >> node[i].p >> node[i].d;
int ans = 0; sort(node + 1, node + 1 + n,cmp);
for (int i = 1; i <= n; ++i) {
for (int j = node[i].d; j >= 1; j--) {
if (!book[j]) {
ans += node[i].p;
book[j] = 1; break;
}
}
}
cout << ans << endl;
}
}
并查集版本
/*
POJ 1456
贪心处理。
按照获利p从大到小排序。
处理的时候选择最后的一个不冲突点。
用并查集实现链表的作用，快速找到不冲突点
*/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e4 + 10;
int f[maxn];
struct Node {
int p, d;
}node[maxn];
int 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() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
int n; while (cin >> n) {
memset(f, -1, sizeof f);
for (int i = 0; i < n; ++i)
cin >> node[i].p >> node[i].d;
sort(node , node + n,cmp);
int ans = 0;
for (int i = 0; i < n; ++i) {
int t = find(node[i].d);
if (t > 0) {
ans += node[i].p;
f[t] = t - 1;
}
}
cout << ans << endl;
}
}