经典算法问题之过河详解

本篇文章的主要内容是关于经典算法问题之过河的详解，感兴趣的朋友可以了解一下，希望对你有所帮助。

描述

一群N人希望用一条船过河，这条船最多只能载两个人。因此，必须安排某种穿梭安排，才能来回划船，以便所有人都能过关。每个人都有不同的划船速度；一对选手的速度取决于速度较慢的人的速度。你的工作是确定一个策略，尽量减少这些人的过河时间。输入

对于每个测试用例，打印一行，其中包含所有N个人过河所需的总秒数。样本输入

141 2 5 10样本输出

17

------------------------------------------------------------------------------------------------------------------------------

问题分析（以下N人速度分别用abcd…表示，且按速度升序排序）

1. 当n= 1时，time则为a
2. 当n= 2时，time则为b
3. 当n= 3时，time则为a+b+c（a与任意一个人过河，a再回来，再和剩下的人过河）
4. 当n>= 4 时，问题就复杂很多，因为任意两人过河，再在过了河中其中一个再回来有很多情况，我们这里需要进行分析观察题目我们可以发现过河中有两个最为重要的点方案【1】过河的两个人，花费时间是由最长的人决定针对这一点，我们可以把最慢d的和次慢c的放一起，这样次慢的时间c就被忽略。方案【2】回来的一个人，花费时间只由他一个人决定针对这一点，我们可以让最快的a把其他人一一送过去，再由最快的a把船送回来

将上面的方案实现当n = 4时（以下N人速度分别用abcd…表示，且按速度升序排序）（）内表示花费时间方案【1】abcdab（b）过去a （a）回来cd（d）过去b（b）回来ab（b）过去所花费时间：a+3b+d

方案【2】abcdad（d）过去a（a）回来ac（c）过去a（a）回来ab（b）过去所花费时间：2a+b+c+d

计算样例现在我们导入题目样例{1，2，5，10}方案【1】时间 = 17方案【2】时间 = 19所以用方案【1】花费时间最短，时间为17

但如果我们修改一下数据{1，2，2，10}方案【1】时间 = 17方案【2】时间 = 16这次却是方案【2】花费的时间最短，时间为16；

如果我们将两个方案的所花费时间约一下则方案【1】：2b方案【2】：a+c可以看出所花费的时间 决定性因素 在于最快的a和次快的b和次慢的c，我们只需要将2b和a+c进行比较，选择花费时间最小的方案即可。

当n > 4 时我们可以表示为用最快的前两个人运送最慢的后两个人便可，运送完人数就减少2。

相关教程：Java视频教程

下面是已经AC了的代码，仅供参考

import java.util.Arrays; import java.util.Scanner;  public class 过河          { 	static long time = 0L; 	public static void main(String[] args) 	{ 		Scanner sc = new Scanner(System.in); 		int m = sc.nextInt(); 		for (int i = 0; i < m; i++) 		{ 			int n = sc.nextInt(); 			int[] A = new int[n]; 			for (int j = 0; j < n; j++) 			{ 				A[j] = sc.nextInt(); 			} 			Arrays.sort(A); 			f(A); 			System.out.println(time); 			time = 0L; 		} 	} 	public static void f(int[] A) { 		if(A.length == 3) { 			time += A[0] + A[1] + A[2]; 			return; 		} 		if(A.length == 2) { 			time += A[1]; 			return; 		} 		if(A.length == 1) { 			time += A[0]; 			return; 		} 		if(A[0] + A[A.length - 2] < A[1] * 2) { 			time += 2 * A[0] + A[A.length - 2] + A[A.length - 1]; 		}else { 			time += A[0] + 2 * A[1] + A[A.length - 1]; 		} 		int[] B = Arrays.copyOfRange(A, 0, A.length - 2); 		f(B); 	} }

以上就是经典算法问题之过河详解的详细内容，更多内容请关注技术你好其它相关文章！