經典演算法問題之過河詳解

本篇文章的主要內容是關於經典演算法問題之過河的詳解，有興趣的朋友可以了解一下，希望對你有幫助。

描述

一群N人希望用一艘船過河，這艘船最多只能載兩個人。因此，必須安排某種穿梭安排，才能來回划船，以便所有人都能過關。每個人都有不同的划船速度；一對選手的速度取決於速度較慢的人的速度。你的工作是確定一個策略，盡量減少這些人的過河時間。
輸入

輸入的第一行包含一個整數T(1輸出量

對於每個測試案例，列印一行，其中包含所有N個人過河所需的總秒數。
樣本輸入

1
4
1 2 5 10
樣本輸出

##17

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

問題分析（以下N人速度分別以abcd…表示，且按速度升序排序）

##當n= 1時，time則為a

1. 當n= 2時，time則為b
2. 當n= 3時，time則為a b c（a與任一過河，a再回來，再和剩下的人過河）
3. 當n>= 4 時，問題就複雜很多，因為任意兩人過河，再在過了河中其中一個再回來有很多情況，我們這裡需要進行分析
觀察題目我們可以發現過河中有兩個最為重要的點
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】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);
	}
}

以上是經典演算法問題之過河詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！