川を渡るという古典的なアルゴリズム問題の詳細な説明

#この記事の主な内容は、川を渡るという古典的なアルゴリズム問題の詳細な説明です。興味のあるお友達は、さらに詳しくお役に立てれば幸いです。

説明

N 人のグループがボートで川を渡りたいと考えています。このボートには最大 2 人しか乗れません。したがって、全員が横断できるように、往復に漕ぐための何らかのシャトルの手配を行う必要があります。漕ぐ速度は人それぞれ異なり、ペアのランナーの速度は遅い人の速度に依存します。あなたの仕事は、これらの人々が川を渡るのにかかる時間を最小限に抑える戦略を決定することです。

入力

入力の最初の行には、テスト ケースの数を表す整数 T (1出力
各テスト ケースについて、N 人全員が川を渡るのにかかった合計秒数を含む行を出力します。

サンプル入力

1

4
1 2 5 10

サンプル出力

17

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

問題分析 (以下のN人の速度をabcd...で表し、速い順に並べる)

#n= 1のとき、時間はa

1. n= 2 のとき、時間は b
2. n= 3 のとき、時間は a b c (a は誰かと川を渡り、a は戻ってきて、残りの人たちと川を渡る) )
3. n>= 4 の場合、2 人が川を渡った場合、そのうちの 1 人が川を渡って戻ってくる状況が多くあるため、問題はさらに複雑になります。ここで分析する必要があります。
質問を観察すると、川を渡るには 2 つの最も重要なポイントがあることがわかります。
4. スキーム [1] 川を渡る 2 人の場合、費やした時間は最も長い人によって決まります。このうち、最も遅い時間 d と 2 番目に遅い時間 c を組み合わせることができ、2 番目に遅い時間 c は無視されます。
   案[2] 戻ってくる人の時間はその人だけで決まる
   そこで、一番早いaが他の人を1人ずつ送り、一番早いaに引き継がせてもいいでしょう。ボートを送り返す
   
   
   
上記の解決策を実現します

n = 4の場合 (以下のN人の速度をabcdで表します... () は費やした時間を示します
スキーム [1] abcdab (b) past a (a) back
cd (d) past
b (b) back
ab(b) past

所要時間
: a 3b d
計画 [2] abcdad(d) past

a(a) 戻る

ac (c) 過去
a (a) 戻る
ab (b) 過去

費やした時間
: 2a b c d
計算例

ここで、質問サンプル {1, 2, 5, 10}Plan [1] Time = 17Plan [2] Time = 19
をインポートします。プラン [1] を使用すると、最も時間がかかります。時間は 17

ですが、データを変更すると {1, 2, 2, 10}
スキーム [1] 時間 = 17

スキーム[2] 時間 = 16

今回は、計画 [2] の時間が 16 で最も短くなります;

2 つの計画にかかる時間を概算すると、
計画 [1] ]: 2b

plan [2]: a c

所要時間
決め手
は、最も速い a、2 番目に速い b、2 番目に遅い c であることがわかります。 2b と a c を比較して、どちらを使うかを選択する必要があります。最も時間がかからない解決策で十分です。
n > 4

の場合、早い人 2 人で遅い 2 人を輸送すると表現でき、輸送後の人数は 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 中国語 Web サイトの他の関連記事を参照してください。