Explication détaillée du problème algorithmique classique de la traversée de la rivière

Le contenu principal de cet article est une explication détaillée du problème classique de l'algorithme de traversée de la rivière. en savoir plus, j'espère que cela vous aidera.

Description

Un groupe de N personnes souhaite traverser la rivière en bateau. Ce bateau ne peut transporter que deux personnes au maximum. Il faut donc mettre en place une sorte de navette pour faire des allers-retours afin que tout le monde puisse traverser. Chacun a une vitesse d'aviron différente ; la vitesse d'une paire de coureurs dépend de la vitesse de la personne la plus lente. Votre travail consiste à déterminer une stratégie qui minimisera le temps nécessaire à ces personnes pour traverser la rivière.
Entrée

La première ligne d'entrée contient un entier T (1<=T<=20), le nombre de cas de test. Viennent ensuite les cas T. La première ligne de chaque cas contient N, et la deuxième ligne contient N entiers donnant le temps nécessaire à chaque personne pour traverser la rivière. Chaque cas est précédé d'une ligne vierge. Il n’y aura pas plus de 1 000 personnes et personne n’aura besoin de plus de 100 secondes pour traverser.
Sortie

Pour chaque cas de test, imprimez une ligne contenant le nombre total de secondes qu'il a fallu aux N personnes pour traverser la rivière.
Exemple d'entrée

1
4
1 2 5 10
Exemple de sortie

17

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

Analyse du problème
(Les vitesses des N personnes suivantes sont représentées par abcd..., et sont triées par ordre croissant de vitesse)

1. Quand n= 1, le temps est un
2. Quand n= 2, le temps est b
3. Quand n=3, le temps est a+b+c (a traverse la rivière avec n'importe quelle personne, a revient, puis traverse la rivière avec les personnes restantes)
4. Quand n>= 4, le problème devient beaucoup plus compliqué, car si deux personnes traversent la rivière, il existe de nombreuses situations où l'une d'elles revient après avoir traversé la rivière. pour l'analyser ici
   En observant la question, on constate qu'il y a Les deux points les plus importants
   Schéma [1] Pour deux personnes traversant la rivière, le temps passé est déterminé par la personne la plus longue
   Pour cela À ce stade, nous pouvons mettre ensemble le d le plus lent et le deuxième c le plus lent. De cette façon, le temps le plus lent c est ignoré.
   Option [2] Le temps passé par une personne qui revient est déterminé par elle seule
   Au vu de cela, on peut laisser le A le plus rapide envoyer les autres un à un, puis laisser le A le plus rapide prendre le relais bateau Renvoyez-le

   Implémentez la solution ci-dessus
   lorsque n = 4 (La vitesse des N personnes ci-dessous est représentée par abcd... , et selon la vitesse Tri par ordre croissant) () indique le temps passé
   Schéma [1] abcd
   ab (b) passé
   a (a) retour
   cd (d) passé
   b (b) retour
   ab(b) passé
   temps passé  : a+3b+d

   Schéma [2] abcd
   ad (d) passé
   a (a ) retour
   ac (c) passé
   a (a) retour
   ab (b) passé
   temps passé  : 2a+b+c+ d

   Exemple de calcul
   Maintenant, nous importons l'exemple de question {1, 2, 5, 10}
   Plan [1] time = 17
   Plan [2] time = 19
   Donc utiliser le plan [1] prend le temps le plus court, le temps est de 17

   Mais si on modifie les données {1, 2, 2, 10}
   Plan [1] time = 17
   Plan [2] Temps = 16
   Cette fois, le plan [2] prend le temps le plus court, avec un temps de 16

   Si on approxime le temps passé par les deux plans, puis
   plan [ 1] : 2b
   Schéma [2] : a+c
   On voit que le temps passéLe facteur décisif réside dans le a le plus rapide, le deuxième- le b le plus rapide et le deuxième c le plus lent. Nous devons seulement comparer 2b et a+c et choisir la solution qui prend le moins de temps.

   Quand n > 4On peut l'exprimer comme utiliser les deux premières personnes les plus rapides pour transporter les deux personnes les plus lentes, et le nombre de personnes sera réduit de 2 après le transport.

   Tutoriels associés : Tutoriel vidéo Java

   Ce qui suit est le code AC, pour référence seulement

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

   Copier après la connexion

   Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!