Detaillierte Erklärung des klassischen algorithmischen Problems der Flussüberquerung

Der Hauptinhalt dieses Artikels ist eine detaillierte Erklärung des klassischen Algorithmusproblems der Flussüberquerung Erfahren Sie mehr. Ich hoffe, es hilft Ihnen.

Beschreibung

Eine Gruppe von N Personen möchte den Fluss in einem Boot überqueren. Dieses Boot kann höchstens zwei Personen befördern. Daher muss eine Art Shuttle-Anordnung eingerichtet werden, um hin und her zu paddeln, sodass jeder hinüberkommen kann. Jeder hat eine andere Rudergeschwindigkeit; die Geschwindigkeit eines Läuferpaares hängt von der Geschwindigkeit der langsameren Person ab. Ihre Aufgabe ist es, eine Strategie zu entwickeln, die die Zeit minimiert, die diese Menschen für die Überquerung des Flusses benötigen.
Eingabe

Die erste Eingabezeile enthält eine Ganzzahl T (171bdfc3587b5b657f91d5158f0a7259b= 4, wird das Problem viel komplizierter, denn wenn zwei beliebige Personen den Fluss überqueren, gibt es viele Situationen, in denen einer von ihnen nach der Überquerung des Flusses zurückkommt um es hier zu analysieren
Wenn wir die Frage beobachten, können wir feststellen, dass es die zwei wichtigsten Punkte gibt
Schema [1] Für zwei Personen, die den Fluss überqueren, wird die Zeit, die sie verbringen, von der längsten Person bestimmt
Dafür Punkt können wir das langsamste d und das zweitlangsamste c zusammenzählen. Auf diese Weise wird die langsamere Zeit c ignoriert.
Option [2] Die Zeit, die eine Person verbringt, die zurückkommt, wird von ihr allein bestimmt.
In Anbetracht dessen können wir den Schnellsten A die anderen nacheinander schicken lassen und dann den Schnellsten A übernehmen lassen Boot Schicken Sie es zurück

Implementieren Sie die obige Lösung
wenn n = 4 (Die Geschwindigkeit von N Personen wird unten durch abcd dargestellt... , und entsprechend der Geschwindigkeit Sortierung in aufsteigender Reihenfolge) () zeigt die aufgewendete Zeit an
Schema [1] abcd
ab (b) Vergangenheit
a (a) zurück
cd (d) Vergangenheit
b (b) zurück
ab(b) Vergangenheit
aufgewendete Zeit : a+3b+d

Schema [2] abcd
ad (d) Vergangenheit
a (a ) zurück
ac (c) Vergangenheit
a (a) zurück
ab (b) Vergangenheit
aufgewendete Zeit : 2a+b+c+ d

Berechnungsbeispiel
Jetzt importieren wir das Fragebeispiel {1, 2, 5, 10}
Plan [1] Zeit = 17
Plan [2] Zeit = 19
Die Verwendung von Plan [1] nimmt also die kürzeste Zeit in Anspruch, die Zeit beträgt 17

Aber wenn wir die Daten {1, 2, 2, 10 ändern🎜>Plan [1] Zeit = 17
Plan [2] Zeit = 16
Dieses Mal benötigt Plan [2] mit einer Zeit von 16 die kürzeste Zeit.

Wenn wir die von den beiden Plänen aufgewendete Zeit annähern, dann

Plan【 1]: 2b
Schema [2]: a+c
Es ist ersichtlich, dass die aufgewendete Zeit
Der entscheidende Faktor liegt im schnellsten a, dem zweiten- schnellstes b und das zweitlangsamste c. Wir müssen nur 2b und a+c vergleichen und die Lösung auswählen, die am wenigsten Zeit in Anspruch nimmt.

Wenn n > 4Wir können es so ausdrücken, dass die ersten beiden schnellsten Personen zum Transport der langsamsten zwei Personen verwendet werden und die Anzahl der Personen nach dem Transport um 2 reduziert wird.

Verwandte Tutorials:

Java-Video-Tutorial

Das Folgende ist der AC-Code, nur als Referenz

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);
	}
}

Das obige ist der detaillierte Inhalt vonDetaillierte Erklärung des klassischen algorithmischen Problems der Flussüberquerung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!