小米2013年校园招聘笔试题-简单并查集

http://www.acmerblog.com/offer-163-1171.html

题目描述：

小明每天都在开源社区上做项目，假设每天他都有很多项目可以选，其中每个项目都有一个开始时间和截止时间，假设做完每个项目后，拿到报酬都是不同的。由于小明马上就要硕士毕业了，面临着买房、买车、给女友买各种包包的鸭梨，但是他的钱包却空空如也，他需要足够的money来充实钱包。万能的网友麻烦你来帮帮小明，如何在最短时间内安排自己手中的项目才能保证赚钱最多（注意：做项目的时候，项目不能并行，即两个项目之间不能有时间重叠，但是一个项目刚结束，就可以立即做另一个项目，即项目起止时间点可以重叠）。

解题思路：这里初始为-1。 可以直接用 f[] 数组记录人数，只不过是负的。节省空间.

02	int n, m, f[100001],i;

03

04	int findSet(int x) {

05	int t = x;

06	while (f[x] > 0)

07

x = f[x];

08	while (t != x) { //路径压缩

09	int q = f[t];

10

f[t] = x;

11

t = q;

12

}

13

return x;

14

}

15

16	void unionSet(int x, int y) {

17	int fx = findSet(x);

18	int fy = findSet(y);

19	if (fx != fy) {

20

n--;

21	int tmp = f[fx] + f[fy];//两个集合个数之和

22	if (f[fx] < f[fy]) {  //大集合 吞并小集合.

23	f[fy] = fx;

24	f[fx] = tmp;

25

} else {

26	f[fx] = fy;

27	f[fy] = tmp;

28

}

29

}

30

}

31

32	int main() {

33	//freopen("in.txt", "r", stdin);

34

int a,b;

35	while(scanf("%d",&n), n) {

36	scanf("%d", &m);

37	for( i=1; i<=n; i++)

38	f[i] = -1;

39	for(i=0; i<m; i++) {

40	scanf("%d %d", &a,&b);

41	unionSet(a,b);

42

}

43	printf("%d\n", n);

44

}

45

return 0;

46

}

DP:
可以按照01背包思路解决。不同之处在于：01背包中是顺序无关的这里按结束的时间先排序。（也可以按开始时间排序，遍历的次序需要颠倒一下

int main(){

16	int n, i, j;

17	//freopen("in.txt", "r", stdin);

18	while(scanf("%d", &n) != EOF){

19	for(i=1; i<=n; i++){

20	scanf("%d %d %d", &p[i].st, &p[i].ed, &p[i].value);

21	dp[i] = 0;

22

}

23	sort(p+1, p+n+1, cmp); //按结束时间排序是重点

24	dp[0] = 0;

25	for(i=1; i<=n; i++){

26

27	//查找最的j，可满足当前的i。都不满足就j=0

28	for(j=i-1; j>0; j--){

29	if(p[i].st >= p[j].ed)

30

break;

31

}

32	dp[i] = dp[j] + p[i].value;

33	if(dp[i] < dp[i-1])

34	dp[i] = dp[i-1];

35

}

36	printf("%d\n",dp[n]);

37

}

38

return 0;

39

}

http://www.acmerblog.com/offer-163-1171.html