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

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

描述

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

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

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

1
4
1 2 5 10
樣本輸出

17

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

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

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

將上面的方案實(shí)現(xiàn)
當(dāng)n = 4時(shí)（以下N人速度分別用abcd…表示，且按速度升序排序）（）內(nèi)表示花費(fèi)時(shí)間
方案【1】abcd
ab（b）過去
a （a）回來
cd（d）過去
b（b）回來
ab（b）過去
所花費(fèi)時(shí)間：a+3b+d

方案【2】abcd
ad（d）過去
a（a）回來
ac（c）過去
a（a）回來
ab（b）過去
所花費(fèi)時(shí)間：2a+b+c+d

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

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

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

當(dāng)n > 4 時(shí)我們可以表示為用最快的前兩個(gè)人運(yùn)送最慢的后兩個(gè)人便可，運(yùn)送完人數(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)容，你們對(duì)java中經(jīng)典算法問題之過河的案例大概了解了嗎？希望文章內(nèi)容對(duì)大家有所幫助。如果想了解更多相關(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://aaarwkj.com/article32/jcdsc.html

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

廣告

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