手电过河

admin

夜晚n位旅行者要过桥，总共只有一个手电筒，一次最多两人过桥，且过桥必须使用手电筒。每位旅行者单独过桥的所需的时间已知，两人结伴渡桥所用的时间为两人中最长的时间。输入人数和每个人过河所需的时间，求解所有人过桥所用的总时间最短是多少。

admin

分析：因为只有一个手电筒，必定有人过桥之后，还要将手电筒送回来。

若n=1,或n=2  所有人直接过河。

若n=3 ,最快的人往返一次把两个人送过去。

若n=4时,假设四人耗时从少到多依次为a ,  b,  y,  z.

那么有两种方案过河，

　　方案一：ab一起过河，a返回，yz一起过河，b返回接a    耗时b+a+z+b+b

　　方案二：ay一起过河，a返回，az一起过河，a返回接b    耗时y+a+z+a+b

　　这两种方案的末状态一定是：最大的两个已经过河，最小的两个留在河这面

　　两方案的时间差为2b-a-y

　　当2b>a+y时，采用方案2， 当2b<=a+y时，采用方案1.

若n>4时，该问题相当于两个快的一直在送最慢的两个，因此递归求解，转化成n-2个旅行者的问题。

1. #include<stdio.h>
   
2. #include<string.h>
   
3. #include<algorithm>
   
4. using namespace std;
   
5. int p[1100];
   
6. int cmp(int a,int b)
   
7.    {
   
8.     return a<b;
   
9.    }
   
10. int Time(int n)
    
11.    {
    
12.     if(n==1)   return p[0];
    
13.     if(n==2)   return p[1];
    
14.     if(n==3)   return p[0]+p[1]+p[2];
    
15.     if(p[1]*2>=p[0]+p[n-2])
    
16.          return 2*p[0]+p[n-1]+p[n-2]+Time(n-2);
    
17.      else
    
18.          return 2*p[1]+p[0]+p[n-1]+Time(n-2);
    
19.    }
    
20.    int main()
    
21.      {
    
22.         int T;
    
23.         int n;
    
24.         int i,j;
    
25.         scanf("%d",&T);
    
26.         while(T--)
    
27.           {
    
28.             scanf("%d",&n);
    
29.             memset(p,0,sizeof(p));
    
30.             for(i=0;i<n;i++)
    
31.              {
    
32.                 scanf("%d",&p[i]);
    
33.              }
    
34.              sort(p,p+n,cmp);
    
35.              printf("%d\n",Time(n));
    
36.           }
    
37.         return 0;
    
38.      }

复制代码