POJ - 1456 贪心+并查集

做法一：直接贪心，按照利润排序，然后直接尽量给每个活动安排到最晚的时间即可。时间复杂度O(n * d)当d都为10000时，很容易超时。由于这题数据比较水，所有贪心未超时。

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 10000 + 5;
struct node{
	int prof, dead;
	bool operator < (const node &p) const {
		return prof > p.prof;
	}
}a[maxn];
int vis[maxn];

int main() {
	int n;
	while(scanf("%d", &n) == 1) {
		for(int i = 0; i < n; ++i) {
			scanf("%d%d", &a[i].prof, &a[i].dead);
		}
		sort(a, a+n);
		memset(vis, 0, sizeof(vis));
		int ans = 0;
		for(int i = 0; i < n; ++i) {
			int flag = 0;
			for(int j = a[i].dead; j > 0; --j) {
				if(!vis[j]) {
					flag = vis[j] = 1;
					break;
				}
			}
			if(flag) ans += a[i].prof;
		}
		printf("%d\n", ans);
	}
	return 0;
}

做法二：先按照利润排序，然后并查集--当某个时间点被占据，它的下一个可用时间点为t - 1，将二者合并即可。复杂度n*logn

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 10000 + 5;
struct node{
	int prof, dead;
	bool operator < (const node &p) const {
		return prof > p.prof;
	}
}a[maxn];
int p[maxn];

int find(int x) {
	return x == p[x] ? x :p[x] = find(p[x]);
} 

void unionset(int x, int y) {
	int rx = find(x), ry = find(y);
	if(rx != ry) p[rx] = ry;
} 

int main() {
	int n;
	while(scanf("%d", &n) == 1) {
		for(int i = 0; i < maxn; ++i) p[i] = i;
		for(int i = 0; i < n; ++i) {
			scanf("%d%d", &a[i].prof, &a[i].dead);
		}
		sort(a, a+n);
		int ans = 0;
		for(int i = 0; i < n; ++i) {
			int u = find(a[i].dead);
			if(u > 0) ans += a[i].prof;
			unionset(a[i].dead, u-1);
		}
		printf("%d\n", ans);
	}
	return 0;
}

做法三：利用优先队列，按照时间从大到小依次放入商品，保证当前的商品的截止期限都大于等于当前时间即可。可以理解为当有多个商品需要在同一天完成优先选择价值最大的。

复杂度O(n * lgn)

AC代码

#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 1e4 + 5;
struct node{
	int prof, dead;

}a[maxn];

bool cmp(const node &a, const node &b) {
	return a.dead > b.dead;
}

bool operator < (const node &p1, const node &p2){
		return p1.prof < p2.prof;
}

int main() {
	int n;
	while(scanf("%d", &n) == 1) {
		int maxt = 0;
		for(int i = 0; i < n; ++i) {
			scanf("%d%d", &a[i].prof, &a[i].dead);
			maxt = max(maxt, a[i].dead);
		}
		sort(a, a+n, cmp);
		priority_queue<node>q;
		int ind = 0, ans = 0;
		for(int i = maxt; i > 0; --i) {
			while(ind < n && a[ind].dead == i) {
				q.push(a[ind++]);
			}
			if(!q.empty()) {
				ans += q.top().prof;
				q.pop();
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

如有不当之处欢迎指出！

巴特西

POJ - 1456 贪心+并查集

最新文章

热门文章