过河问题
时间限制： 1000 ms | 内存限制： 65535 KB
难度： 5
- 描述
-
在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过。如果各自单独过桥的话，N人所需要的时间已知；而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥。
输入
第一行是一个整数T(1<=T<=20)表示测试数据的组数
每组测试数据的第一行是一个整数N(1<=N<=1000)表示共有N个人要过河每组测试数据的第二行是N个整数Si,表示此人过河所需要花时间。(0<Si<=100)
- 输出
- 输出所有人都过河需要用的最少时间 样例输入
-
141 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)所以解决了这个，问题就解决了，当然当为三个人时，方法固定，先一和三，然后一回去，再加上二就行了；具体代码如下：
1 #include
2 #define MAX 1000 3 int main() 4 { 5 int n_sample, n_person, a[MAX], total_time, i, j, t; 6 scanf("%d",&n_sample); //样例数量 7 while(n_sample--) 8 { 9 scanf("%d",&n_person); //输入人数10 for(i = 1; i <= n_person; ++i)11 scanf("%d",&a[i]); //输入每个人的过河时间，空格分开,开始下标用112 total_time = 0;13 14 if(n_person != 1)//选择法进行排序15 {16 for(i = 1; i <= n_person - 1; i++)17 for(j = i+1; j <= n_person; ++j)18 if(a[j] < a[i])19 {t = a[j];a[j] = a[i];a[i] = t;}20 21 for(i = n_person; i >= 3;)22 {23 if(i == 3) //如果是3个人24 {25 total_time += a[3]+a[1];26 break;27 }28 if( 2*a[2] < a[1]+a[i-1])29 {30 total_time += a[1] + 2*a[2] + a[i];31 i-= 2;32 }33 else34 {35 total_time += a[i] + a[1];36 i--;37 }38 }39 total_time += a[2];40 }41 else42 total_time = a[1]; //如果只有一个人43 printf("%d\n",total_time);44 }45 return 0;46 }