一个简单的智力问题如下：有四个人要过一条河，河上一个桥，每次最多只允许两个人过，且过河必须手电筒，只有一把手电筒，每个人完成过河的时间是不同的，两个人过河的总时间为慢者单独过河的时间。求四个人最终都过河需要的总时间。如，第一个人单独过河需要1min，第二个人单独过河需要2min，第三个人过河需要5min，第四个人过河需要10min，则总的过河时间为：1和2先过河，然后1把手电筒送回来，总共需要3min，然后3和4过河，2把手电筒送回来，需要10+2=12min，然后1和2再过河，总共需要3+12+2 = 17min。
这个问题其实也可以采用图论的方式来解决，这个方法很新颖，也很巧妙，具体请参考
http://blog.csdn.net/w468917145/article/details/4601882
这里想要讲的是题目的要求不变，但是现在不仅仅四个人，而是有n个人，给定这n个人每个人单独过桥的时间，求n个人最终均过河所需要的最短时间。
该怎么做呢？其实想想刚才的四个人的过程，1和2先过河的原因是希望能留下一个人，等最慢的和次慢的过河之后之前留下的这个人能够把手电筒送回来。那么其实每次重复的过程就是最快的和次快的先过，然后最快的送手电筒回来，然后最慢的和次慢的再一起过河（这样能够让本来都要耗费很长时间的两个人一次性过河，从而节省时间），然后再让次慢的回来送手电筒，这样其实就将问题规模从1~n=>1~n-2，而问题状态不变。从而可以重复上述过程直到只剩下3个人或者2个人。
上述的解法在每次运送完当前最慢和次慢的两个人所耗费的时间为time[n] + 2*time[2] + time[1]。但是有没有想过根本不让次快的参与运送过程，每次都让最快的运送，这样时间就是time[n] + time[n - 1] + 2*time[1]。因此，每次运送最慢的和次慢的两个人之前都要判断到底是需要2参与运送还是只需要1参与运送就可了。
借用问题
http://acm.nyist.net/JudgeOnline/problem.php?pid=47 程序代码如下：
1 #include <cstdio>
2 #include <cstdlib>
3
4 #define MAX 1005
5
6 int people[MAX];
7
8 int cmp(const void *a, const void *b) {
9 int *x = (int *)a;
10 int *y = (int *)b;
11 return *x > *y;
12 }
13
14 int main() {
15 int cases;
16 scanf("%d", &cases);
17 while (cases--) {
18 int n, i;
19 int res = 0;
20 scanf("%d", &n);
21 for (i = 0; i < n; ++i) {
22 scanf("%d", &people[i]);
23 }
24 qsort(people, n, sizeof(int), cmp);
25 if (n == 1) {
26 printf("%d\n", people[0]);
27 continue;
28 } else if (n == 2) {
29 printf("%d\n", people[1]);
30 continue;
31 } else {
32 int i = n - 1;
33 while (i > 2) {
34 int res1 = people[0] + (people[1] << 1) + people[i];
35 int res2 = people[i] + people[i - 1] + (people[0] << 1);
36 res = res1 > res2 ? res2 : res1;
37 i -= 2;
38 }
39 if (i == 2) {
40 res += people[0] + people[1] + people[2];
41 } else {
42 res += people[1];
43 }
44 }
45 printf("%d\n", res);
46 }
47 return 0;
48 }
呵呵
posted on 2012-09-17 18:56
myjfm 阅读(2194)
评论(1) 编辑 收藏 引用 所属分类:
算法基础