java中經典算法問題之過河的案例

java中經典算法問題之過河的案例？這個問題可能是我們日常學習或工作經常見到的。希望通過這個問題能讓你收獲頗深。下面是小編給大家帶來的參考內容，讓我們一起來看看吧！

描述

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

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

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

1
4
1 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】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。

下面是已經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);
	}
}

感謝各位的閱讀！看完上述內容，你們對java中經典算法問題之過河的案例大概了解了嗎？希望文章內容對大家有所幫助。如果想了解更多相關文章內容，歡迎關注億速云行業資訊頻道。