java中經(jīng)典算法問題之過河的案例？這個問題可能是我們?nèi)粘W(xué)習(xí)或工作經(jīng)常見到的。希望通過這個問題能讓你收獲頗深。下面是小編給大家?guī)淼膮⒖純?nèi)容，讓我們一起來看看吧！

在固陽等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè) 網(wǎng)站設(shè)計制作專業(yè)公司,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站設(shè)計,成都營銷網(wǎng)站建設(shè),外貿(mào)網(wǎng)站制作,固陽網(wǎng)站建設(shè)費用合理。

描述

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

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

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

1
4
1 2 5 10
樣本輸出

17

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

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

1. 當(dāng)n= 1時，time則為a
2. 當(dāng)n= 2時，time則為b
3. 當(dāng)n= 3時，time則為a+b+c（a與任意一個人過河，a再回來，再和剩下的人過河）
4. 當(dāng)n>=  4 時，問題就復(fù)雜很多，因為任意兩人過河，再在過了河中其中一個再回來有很多情況，我們這里需要進(jìn)行分析
   觀察題目我們可以發(fā)現(xiàn)過河中有兩個最為重要的點
   方案【1】過河的兩個人，花費時間是由最長的人決定
   針對這一點，我們可以把最慢d的和次慢c的放一起，這樣次慢的時間c就被忽略。
   方案【2】回來的一個人，花費時間只由他一個人決定
   針對這一點，我們可以讓最快的a把其他人一一送過去，再由最快的a把船送回來

將上面的方案實現(xiàn)
當(dāng)n = 4時（以下N人速度分別用abcd…表示，且按速度升序排序）（）內(nèi)表示花費時間
方案【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

計算樣例
現(xiàn)在我們導(dǎo)入題目樣例{1，2，5，10}
方案【1】時間 = 17
方案【2】時間 = 19
所以用方案【1】花費時間最短，時間為17

但如果我們修改一下數(shù)據(jù){1，2，2，10}
方案【1】時間 = 17
方案【2】時間 = 16
這次卻是方案【2】花費的時間最短，時間為16；

如果我們將兩個方案的所花費時間約一下則
方案【1】：2b
方案【2】：a+c
可以看出所花費的時間 決定性因素 在于最快的a和次快的b和次慢的c，我們只需要將2b和a+c進(jìn)行比較，選擇花費時間最小的方案即可。

當(dāng)n > 4 時我們可以表示為用最快的前兩個人運送最慢的后兩個人便可，運送完人數(shù)就減少2。

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

感謝各位的閱讀！看完上述內(nèi)容，你們對java中經(jīng)典算法問題之過河的案例大概了解了嗎？希望文章內(nèi)容對大家有所幫助。如果想了解更多相關(guān)文章內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

網(wǎng)站欄目：java中經(jīng)典算法問題之過河的案例-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://www.rwnh.cn/article32/jcdsc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、App設(shè)計、云服務(wù)器、營銷型網(wǎng)站建設(shè)、小程序開發(fā)、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)