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

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

描述

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

輸入的第一行包含一個整數T(1<=T<=20)，測試用例數。接下來是T個案例。每個案例的第一行包含N，第二行包含N個整數，給出每個人過河的時間。每個案例前面都有一個空白行。不會有超過1000人，沒有人需要超過100秒的跨越。
輸出量

對於每個測試案例，列印一行，其中包含所有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中文網其他相關文章！