ny47 过河问题

过河问题

时间限制：1000 ms  |  内存限制：65535 KB

难度：5

 

描述

在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。 

输入

第一行是一个整数T(1<=T<=20)表示测试数据的组数
每组测试数据的第一行是一个整数N(1<=N<=1000)表示共有N个人要过河
每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。(0<Si<=100)

       输出

输出所有人都过河需要用的最少时间

样例输入

1
4
1 2 5 10

样例输出

17
讲解本题：这是一种简单的动态规划问题，思考的时候比较复杂，不太容易理解，大致意思是当两个人过去后，有一个人还要回来（把灯送回来，但是送灯回来的时间也要加上），由此考虑求解；
 
现在假设n个人的过河时间已经从小到大排好序用数列 a1 ,a2 ,a3 ,a4 ,... , an ;

当(n =1) time= a[n] ;
当(n >=2) 时：假如n=4时；

（1） 
a3 ,a4 怎么过，
肯定是a1 , a2 先过去再a1回来。 

然后第一种方法(a)a1和a3 一起过,再a1回来和a4一起过 。

总时间 time1 = a1 + a3 + a1 + a4 ;

第二种方法(b)a3和a4一起过再a2回来和a1一起过。

总时间 time2 =a1 + a4 + a2 + a2 ;

time = min(time1 , time2);取最短的方法；
实质上就是这个判断句if(2*a[2] < a[1]+a[i-1])

 
例如第一步 a1,a2，先过，时间a2，a1回来，时间a1
    第二步，a3，a4，过，时间a4，a2，回来，时间a2，      或者   a1,a4,先过，时间a4，然后，a1回来，时间a1
    第三步，a2，a1，过，时间a2，                       或者   a1，a3，过，时间a3，，
    第一种  a2+a1+a4+a2+a2                            第二种 a2+a4+a1+a1+a3
比较两种差别在a2+a2 a1+a3(a3其实就是i-1)
所以解决了这个，问题就解决了，当然当为三个人时，方法固定，先一和三，然后一回去，再加上二就行了；具体代码如下：

#include<stdio.h>
#define MAX 1000
int main()
{
int n_sample, n_person, a[MAX], total_time, i, j, t;
scanf("%d",&n_sample); //样例数量
     while(n_sample--)
  {
scanf("%d",&n_person); //输入人数
for(i = 1; i <= n_person; ++i)
scanf("%d",&a[i]); //输入每个人的过河时间，空格分开,开始下标用1
total_time = 0;

      if(n_person != 1)//选择法进行排序
  {
            for(i = 1; i <= n_person - 1; i++)
              for(j = i+1; j <= n_person; ++j)
                 if(a[j] < a[i])
                  {t = a[j];a[j] = a[i];a[i] = t;}

          for(i = n_person; i >= 3;)
            {
                if(i == 3) //如果是3个人
            {
                    total_time += a[3]+a[1];
         break;
     }
                if( 2*a[2] < a[1]+a[i-1])
             {
                    total_time += a[1] + 2*a[2] + a[i];
                     i-= 2;
             }
                else
             {
                    total_time += a[i] + a[1];
                    i--;
              }
    }
          total_time += a[2];
   }
      else
          total_time = a[1]; //如果只有一个人
         printf("%d
",total_time);
  }
return 0;
}