poj1456 Supermarket

参见算法竞赛进阶指南77页

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, dui[10005], k;
struct Node{
	int p, d;
}nd[10005];
bool cmp(Node x, Node y){
	if(x.d==y.d)	return x.p<y.p;
	else	return x.d<y.d;
}
int cmp2(int x, int y){
	return x>y;
}
int main(){
	while(scanf("%d", &n)!=EOF){
		k = 0;
		for(int i=1; i<=n; i++)
			scanf("%d %d", &nd[i].p, &nd[i].d);
		sort(nd+1, nd+1+n, cmp);
		for(int i=1; i<=n; i++){
			if(k<nd[i].d){
				dui[++k] = nd[i].p;
				push_heap(dui+1, dui+1+k, cmp2);
			}
			else if(nd[i].p>dui[1]){
				pop_heap(dui+1, dui+1+k, cmp2);
				dui[k] = nd[i].p;
				push_heap(dui+1, dui+1+k, cmp2);
			}
		}
		int ans=0;
		while(k){
			ans += dui[1];
			pop_heap(dui+1, dui+1+k, cmp2);
			k--;
		}
		printf("%d
", ans);
	}
	return 0;
}

参考算法竞赛进阶指南188页

#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int n, fa[10005], ans;
struct Node{
	int p, d;
}nd[10005];
bool cmp(Node x, Node y){
	return x.p>y.p;
}
int myfind(int x){
	return fa[x]==x?x:fa[x]=myfind(fa[x]);
}
int main(){
	while(scanf("%d", &n)!=EOF){
		for(int i=1; i<=n; i++)
			scanf("%d %d", &nd[i].p, &nd[i].d);
		sort(nd+1, nd+1+n, cmp);
		for(int i=0; i<=10000; i++)
			fa[i] = i;
		ans = 0;
		for(int i=1; i<=n; i++)
			if(myfind(nd[i].d)){
				ans += nd[i].p;
				fa[myfind(nd[i].d)] = myfind(nd[i].d) - 1;
			}
		printf("%d
", ans);
	}
	return 0;
}