过河问题
时间限制：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
这个题确实不太好想，我是这样考虑的：
首先把所有人过河的时间由小到大排序
然后会发现，如果假设每次都是最快的一个带着当前最慢的人过河，然后最快的人回来，进行下一次，似乎是最快的方法。
但是还有另一种过河方式：就是首先最快的两个人一起过河，然后最快的人回来，最慢的两个人过河（这时用的时间是两人中最慢的那个人的），这时候再让第一次已经过去但是没有回来的第二快的人回来，比如最快的两个人是1、2，最慢两个人是99、100，那么我们会发现前一种办法时间是 100 + 1 +99 + 1 = 201，但是这种办法是2 + 1 + 100 + 2 = 105，这是极端数据，在普通数据里这两种办法不一定哪个更快，所以要判断一下
#include<stdio.h>
#include<stdlib.h> int comp(const void *a , const void *b)
{
return *(int*)a - *(int *)b;
} int main()
{
int i , j , k;
int p[1000];
int flag , time1 , time2; scanf("%d" , &i);
while(i--)
{
scanf("%d" , &j);
flag = 0;
for(k = 0 ; k < j ; k++)
{
scanf("%d" , &p[k]);
}
qsort(p , j , sizeof(int) , comp);
for( --k ; k > 2 ; k -= 2)
{
time1 = p[0] + p[k] + p[1] * 2;
time2 = 2 * p[0] + p[k - 1] + p[k];
if(time1 > time2)
flag += time2;
else
flag += time1;
}
if(k == 2)
{
flag += p[1] + p[0] + p[2];
}
else if(k == 0)
flag = p[0];
else
flag += p[1];
printf("%d\n" , flag);
} return 0;
}