随笔-80  评论-24  文章-0  trackbacks-0
一个简单的智力问题如下:有四个人要过一条河,河上一个桥,每次最多只允许两个人过,且过河必须手电筒,只有一把手电筒,每个人完成过河的时间是不同的,两个人过河的总时间为慢者单独过河的时间。求四个人最终都过河需要的总时间。如,第一个人单独过河需要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 阅读(1659) 评论(1)  编辑 收藏 引用 所属分类: 算法基础

评论:
# re: 过河问题[未登录] 2014-07-27 07:44 | bluesea
我也没想到后面那个...
话说这样能证明正确性么? 一定是时间最短的? 感觉很intuitive, 但是证明起来不是那么直接...   回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理