过河问题
时间限制: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
- 来源
-
/*题解: 每次过两个人,要考虑2种情况: 第一种:a[0],a[1]过,a[0]回来(递手电筒);a[n-1],a[n-2]过,a[1]回来。 耗时:a[1]+a[0]+a[n-1]+a[1] = a[0]+2*a[1]+a[n-1]; 第二种:a[0],a[n-1]过,a[0]回来;a[0],a[n-2]过,a[0]回来。 耗时:a[n-1]+a[0]+a[n-2]+a[0] = 2*a[0]+a[n-1]+a[n-2]; 从上面可以看出,每次a[0],a[1]都要回来,改变的只是a[n-1]、a[n-2]. 最后有剩余2、3个人,两种情况。由于初始化sum = a[1],故剩余2人的可以直接输出。 剩余三人的sum += a[0]+a[2]; */
代码如下: #include<cstdio> #include<algorithm> using namespace std; int main() { int T,i,n,m,a[1010],sum; scanf("%d",&T); while(T--) { scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&a[i]); } if(n==1) //就一个人,直接输出 { printf("%d\n",a[0]); continue; } sort(a,a+n); sum = a[1]; //sum初始为a[1]. while(n>3) { if(a[0]+2*a[1]+a[n-1]>2*a[0]+a[n-1]+a[n-2]) sum += 2*a[0]+a[n-1]+a[n-2]; else sum += a[0]+2*a[1]+a[n-1]; n -= 2; } if(n==3) sum += a[0]+a[n-1]; printf("%d\n",sum); } return 0; }