典范算法题目之过河详解【JAVA教程】,Java,算法

本篇文章的主要内容是关于典范算法问题之过河的详解，感兴趣的朋侪能够相识一下，愿望对你有所协助。

形貌

一群N人愿望用一条船过河，这条船最多只能载两个人。因而，必需部署某种穿越部署，才往返荡舟，以便一切人都能过关。每一个人都有差别的荡舟速率；一对选手的速率取决于速率较慢的人的速率。你的事情是肯定一个战略，只管削减这些人的过河时候。
输入

输入的第一行包括一个整数T(1<=T<=20)，测试用例数。接下来是T个案例。每一个案例的第一行包括N，第二行包括N个整数，给出每一个人过河的时候。每一个案例前面都有一个空白行。不会有凌驾1000人，没有人须要凌驾100秒的逾越。
输出量

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

1
4
1 2 5 10
样本输出

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

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

当n= 1时，time则为a
当n= 2时，time则为b
当n= 3时，time则为a+b+c（a与恣意一个人过河，a再返来，再和剩下的人过河）
当n>= 4 时，问题就庞杂许多，由于恣意两人过河，再在过了河中个中一个再返来有许多状况，我们这里须要举行剖析
视察问题我们能够发明过河中有两个最为主要的点
计划【1】过河的两个人，消费时候是由最长的人决议
针对这一点，我们能够把最慢d的和次慢c的放一同，如许次慢的时候c就被疏忽。
计划【2】返来的一个人，消费时候只由他一个人决议
针对这一点，我们能够让最快的a把其他人逐一送过去，再由最快的a把船送返来

将上面的计划完成
当n = 4时（以下N人速率分别用abcd…示意，且按速率升序排序）（）内示意消费时候
计划【1】abcd
ab（b）过去
a （a）返来
cd（d）过去
b（b）返来
ab（b）过去
所消费时候：a+3b+d

计划【2】abcd
ad（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);
	}
}

以上就是典范算法问题之过河详解的细致内容，更多请关注ki4网别的相干文章！