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

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

Apr 30, 2019 pm 03:26 PM
java 算法

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Racine carrée en Java Racine carrée en Java Aug 30, 2024 pm 04:26 PM

Guide de la racine carrée en Java. Nous discutons ici du fonctionnement de Square Root en Java avec un exemple et son implémentation de code respectivement.

Nombre parfait en Java Nombre parfait en Java Aug 30, 2024 pm 04:28 PM

Guide du nombre parfait en Java. Nous discutons ici de la définition, comment vérifier le nombre parfait en Java ?, des exemples d'implémentation de code.

Générateur de nombres aléatoires en Java Générateur de nombres aléatoires en Java Aug 30, 2024 pm 04:27 PM

Guide du générateur de nombres aléatoires en Java. Nous discutons ici des fonctions en Java avec des exemples et de deux générateurs différents avec d'autres exemples.

Weka en Java Weka en Java Aug 30, 2024 pm 04:28 PM

Guide de Weka en Java. Nous discutons ici de l'introduction, de la façon d'utiliser Weka Java, du type de plate-forme et des avantages avec des exemples.

Numéro Armstrong en Java Numéro Armstrong en Java Aug 30, 2024 pm 04:26 PM

Guide du numéro Armstrong en Java. Nous discutons ici d'une introduction au numéro d'Armstrong en Java ainsi que d'une partie du code.

Numéro de Smith en Java Numéro de Smith en Java Aug 30, 2024 pm 04:28 PM

Guide du nombre de Smith en Java. Nous discutons ici de la définition, comment vérifier le numéro Smith en Java ? exemple avec implémentation de code.

Questions d'entretien chez Java Spring Questions d'entretien chez Java Spring Aug 30, 2024 pm 04:29 PM

Dans cet article, nous avons conservé les questions d'entretien Java Spring les plus posées avec leurs réponses détaillées. Pour que vous puissiez réussir l'interview.

Break or Return of Java 8 Stream Forach? Break or Return of Java 8 Stream Forach? Feb 07, 2025 pm 12:09 PM

Java 8 présente l'API Stream, fournissant un moyen puissant et expressif de traiter les collections de données. Cependant, une question courante lors de l'utilisation du flux est: comment se casser ou revenir d'une opération FOREAK? Les boucles traditionnelles permettent une interruption ou un retour précoce, mais la méthode Foreach de Stream ne prend pas directement en charge cette méthode. Cet article expliquera les raisons et explorera des méthodes alternatives pour la mise en œuvre de terminaison prématurée dans les systèmes de traitement de flux. Lire plus approfondie: Améliorations de l'API Java Stream Comprendre le flux Forach La méthode foreach est une opération terminale qui effectue une opération sur chaque élément du flux. Son intention de conception est

See all articles