本文共 2581 字，大约阅读时间需要 8 分钟。

有N个人想要过一条河，但是他们只有一条最多载两人的船。因此必须想出一个调度船来回的方法让每个人都能过河。每个人都有自己的划船速度，且同一条船上的两个人取决于慢者的速度。你的任务就是想出一个每人都能过河的最快策略。

输入格式:

输入的第一行是一个正整数T(1 <= T <= 20),表示测试用例的组数。下面是T组用例。每个用例的第一行是正整数N，第二行是N个正整数表示每个人的划船速度。每组用例不会超出1000个人，每个人的划船时间不会超过100秒。

输出格式:

对于每个用例，输出所有N个人都能过河的最短时间（秒）。

输入样例:

2

3 1 3 7 4 1 2 5 10

输出样例:

11

17

思路分析

1、这道题的思路基本分为两个方向： 第一点就是跑得快的人多跑几趟， 第二点就是我们需要将复杂问题转换为简单问题的集合，本思路容后再表。 2、从测试样例的第二组数据可知，A、B、C、D四个人渡河时间分别为1、2、5、10。则17分钟来源方案如下 第一步：A和B过桥，花费2分钟。 第二步：A回来，花费1分钟。 第三步：C和D过桥，花费10分钟。 第四步：B回来，花费2分钟。 第五步：A和B过桥，花费2分钟。 一共17分钟。 3、通过测试样例的分析可以知道：1、因为我们需要最快的两人来回过河，所以这个问题可以简化为最快的两个人和最慢的两个人为一组过河，将总体分为很多组的时间相加的问题。每四人一组，计算到第四步时，AB两人仍在对岸，而最慢的两人已经成功渡河。接下来AB就可以重复前四步，将慢的人送过河去。 例如现在有四个人A、B、C、D，过河时间分别为1，2，5，8分钟。 则解法为： 第一步：A和B过桥，花费2分钟。 第二步：A回来，花费1分钟。 第三步：C和D过桥，花费8分钟。 第四步：B回来，花费2分钟。 第五步：A和B过桥，花费2分钟。 一共是15分钟。 4、但如果采用这种方式过河并不是在所有情况下都是最短的时间，例如A、B、C、D，过河时间分别为1，8，9，10分钟 则： 方案一 第一步：A和B过桥，花费8分钟。 第二步：A回来，花费1分钟。 第三步：C和D过桥，花费10分钟。 第四步：B回来，花费8分钟。 第五步：A和B过桥，花费8分钟。 一共要8+1+10+8+8=35分钟。 方案二 第一步：A和B过桥，花费8分钟。 第二步：A回来，花费1分钟。 第三步：A和C过桥，花费9分钟。 第四步：A回来，花费1分钟。 第五步：A和D过桥，花费10分钟。 一共要8+1+9+1+10=29分钟。 5、如果我们以将最慢的两人先送过河为目的，那么通过上述并观察可知，方案二可以被优化为： 第一步：A和C过桥，花费C分钟。 第二步：A回来，花费A分钟。 第三步：A和D过桥，花费D分钟。 第四步：A回来，花费A分钟。 花费时间为：A+A+C+D 如此的话，送完最慢的2人后，A依然未过河，而B根本没动过。 6、可知，最优方案有两种，5中方案为一种，另一种为 第一步：A和B过桥，花费B分钟。 第二步：A回来，花费A分钟。 第三步：D和C过桥，花费D分钟。 第四步：B回来，花费B分钟。 花费时间为：A+B+D+B 7、只要每一次比较两种方案所用时间，采用时间短的方案，每次未过河的人都少两个最慢的。即可解决问题。 8、我们还需要考虑几种极端情况：ABC三个人时间为A+B+C；AB过桥B分钟；只有一个人则只有A分钟。

import java.util.Scanner;public class Main {
   	public static void main(String[] args) {
   		Scanner se= new Scanner (System.in);		int n=Integer.parseInt(se.nextLine());		for(int i=0;i
   
    =0;q-=2) {
   					if(q==2) {
   						t=t+a[0]+a[1]+a[2];						break;					}					else if(q==1) {
   						t=t+a[1];						break;					}else if(q==0) {
   						t=t+a[0];						break;					}else {
   						int t1=a[0]+a[0]+a[q]+a[q-1];						int t2=a[0]+a[1]+a[1]+a[q];						if(t1>=t2) {
   							t+=t2;						}else {
   							t+=t1;						}					}				}				System.out.println(t);			}		}	}	public static void quickSort(int[] arr,int left, int right) {
   		int l = left;		int r = right; 		int pivot = arr[(left + right) / 2];		int temp = 0; 		while( l < r) {
    			while( arr[l] < pivot) {
   				l += 1;			}			while(arr[r] > pivot) {
   				r -= 1;			}			if( l >= r) {
   				break;			}			temp = arr[l];			arr[l] = arr[r];			arr[r] = temp;			if(arr[l] == pivot) {
   				r -= 1;			}			if(arr[r] == pivot) {
   				l += 1;			}		}		if (l == r) {
   			l += 1;			r -= 1;		}		if(left < r) {
   			quickSort(arr, left, r);		}		if(right > l) {
   			quickSort(arr, l, right);		}	}}
   

转载地址：http://vhbdi.baihongyu.com/