NYOJ208 Supermarket（续）

前面用贪心算法解决的方案也可以AC，但是对于每一个数据，都要从它的deadline开始寻找，最坏的情况是O(n^2)。所以这里用并查集来优化查找的步骤。
怎么优化，其实这个思想在NYOJ207食物链那道题里面就有体现。并查集有两个功能，查找根节点和合并根节点，如果每一条路径都比较短的话，查找的效率就会很高。怎么样使每条路径都比较短呢？那就是尽可能的将所有节点直接连接到根节点，也就是呈现一个星形。比如要加入一个节点，就必须逐步的更新根节点到该节点父节点以前的所有节点的父节点，使它们都直接与根节点相连。这种条件下，内存要多一点（N*3字节），但时间会快很多（至少200ms）。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
const int N = 10005;
int arr[N][2];
int parent[N];
int compare(const void *a, const void *b)
{
	int *p1 = (int *)a;
	int *p2 = (int *)b;
	return p2[0] - p1[0];
}
int Find(int x)
{
	if(parent[x] == -1)
		return x;
	parent[x] = Find(parent[x]);
	return parent[x];
}
int main()
{
	int n,i;
	int r,sum;
	while(scanf("%d", &n) != EOF)
	{
		memset(parent, -1, sizeof(parent));
		for(i = 0; i < n; ++i)
			scanf("%d %d", &arr[i][0], &arr[i][1]);
		qsort(arr, n, 2*sizeof(int), compare);
		sum = 0;
		for(i = 0; i < n; ++i)
		{
			r = Find(arr[i][1]);
			if(r > 0)//如果有日期可用
			{
				sum += arr[i][0];
				parent[r] = Find(r - 1);
			}
		}
		printf("%d\n", sum);
	}
}