検索
ホームページJava&#&チュートリアル川を渡るという古典的なアルゴリズム問題の詳細な説明

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

説明

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


  6. 上記の解決策を実現します

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 サイトの他の関連記事を参照してください。

声明
この記事はCSDNで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。
高度なJavaプロジェクト管理、自動化の構築、依存関係の解像度にMavenまたはGradleを使用するにはどうすればよいですか?高度なJavaプロジェクト管理、自動化の構築、依存関係の解像度にMavenまたはGradleを使用するにはどうすればよいですか?Mar 17, 2025 pm 05:46 PM

この記事では、Javaプロジェクト管理、自動化の構築、依存関係の解像度にMavenとGradleを使用して、アプローチと最適化戦略を比較して説明します。

適切なバージョン化と依存関係管理を備えたカスタムJavaライブラリ(JARファイル)を作成および使用するにはどうすればよいですか?適切なバージョン化と依存関係管理を備えたカスタムJavaライブラリ(JARファイル)を作成および使用するにはどうすればよいですか?Mar 17, 2025 pm 05:45 PM

この記事では、MavenやGradleなどのツールを使用して、適切なバージョン化と依存関係管理を使用して、カスタムJavaライブラリ(JARファイル)の作成と使用について説明します。

カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?Mar 17, 2025 pm 05:44 PM

この記事では、カフェインとグアバキャッシュを使用してJavaでマルチレベルキャッシュを実装してアプリケーションのパフォーマンスを向上させています。セットアップ、統合、パフォーマンスの利点をカバーし、構成と立ち退きポリシー管理Best Pra

キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPA(Java Persistence API)を使用するにはどうすればよいですか?キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPA(Java Persistence API)を使用するにはどうすればよいですか?Mar 17, 2025 pm 05:43 PM

この記事では、キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPAを使用することについて説明します。潜在的な落とし穴を強調しながら、パフォーマンスを最適化するためのセットアップ、エンティティマッピング、およびベストプラクティスをカバーしています。[159文字]

Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか?Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか?Mar 17, 2025 pm 05:35 PM

Javaのクラスロードには、ブートストラップ、拡張機能、およびアプリケーションクラスローダーを備えた階層システムを使用して、クラスの読み込み、リンク、および初期化が含まれます。親の委任モデルは、コアクラスが最初にロードされ、カスタムクラスのLOAに影響を与えることを保証します

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

WebStorm Mac版

WebStorm Mac版

便利なJavaScript開発ツール

MantisBT

MantisBT

Mantis は、製品の欠陥追跡を支援するために設計された、導入が簡単な Web ベースの欠陥追跡ツールです。 PHP、MySQL、Web サーバーが必要です。デモおよびホスティング サービスをチェックしてください。

SublimeText3 Linux 新バージョン

SublimeText3 Linux 新バージョン

SublimeText3 Linux 最新バージョン

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター