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 (1<=T<=20), die Anzahl der Testfälle. Als nächstes kommen T-Fälle. Die erste Zeile jedes Falles enthält N, und die zweite Zeile enthält N ganze Zahlen, die die Zeit angeben, die jede Person für die Überquerung des Flusses benötigt. Vor jedem Fall steht eine Leerzeile. Es werden nicht mehr als 1.000 Personen anwesend sein und niemand wird mehr als 100 Sekunden brauchen, um die Überquerung zu überqueren.
Ausgabe

Drucken Sie für jeden Testfall eine Zeile aus, die die Gesamtzahl der Sekunden enthält, die alle N Personen benötigt haben, um den Fluss zu überqueren.
Beispieleingabe

1
4
1 2 5 10
Beispielausgabe

17

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

Problemanalyse
(Die Geschwindigkeiten der folgenden N Personen werden durch abcd... dargestellt und in aufsteigender Reihenfolge der Geschwindigkeit sortiert)

1. Wenn n= 1, ist die Zeit a
2. Wenn n=2, ist die Zeit b
3. Wenn n=3, ist die Zeit a+b+c (a überquert den Fluss mit einer beliebigen Person, a kommt zurück und überquert dann den Fluss mit den verbleibenden Personen)
4. Wenn n>= 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!