Distance totale minimale parcourue

2463. Distance totale minimale parcourue

Difficulté : Difficile

Sujets :Array, programmation dynamique, tri

Il y a quelques robots et usines sur l'axe X. Vous recevez un robot à tableau entier où robot[i] est la position du i^ème robot. Vous recevez également une fabrique de tableaux d'entiers 2D où factory[j] = [position_j, limit_j] indique que position_j est la position du j _èmeusine et que la j_èmeusine peut réparer au plus limite_j robots.

Les positions de chaque robot sont uniques. Les positions de chaque usine sont également uniques. A noter qu'un robot peut être dans la même position qu'une usine au départ.

Tous les robots sont initialement cassés ; ils continuent d’avancer dans une direction. La direction peut être la direction négative ou positive de l’axe X. Lorsqu'un robot arrive dans une usine qui n'a pas atteint sa limite, l'usine répare le robot et il s'arrête de bouger.

A tout moment, vous pouvez définir la direction initiale de déplacement de certains robots. Votre objectif est de minimiser la distance totale parcourue par tous les robots.

Renvoyer la distance totale minimale parcourue par tous les robots. Les cas de tests sont générés de telle sorte que tous les robots puissent être réparés.

Notez que

• Tous les robots se déplacent à la même vitesse.
• Si deux robots se déplacent dans la même direction, ils n'entreront jamais en collision.
• Si deux robots se déplacent dans des directions opposées et qu'ils se rencontrent à un moment donné, ils n'entrent pas en collision. Ils se croisent.
• Si un robot passe devant une usine qui a atteint ses limites, il la traverse comme si elle n'existait pas.
• Si le robot s'est déplacé d'une position x à une position y, la distance parcourue est |y - x|.

Exemple 1 :

• Entrée : robot = [0,4,6], usine = [[2,2],[6,2]]
• Sortie : 4
• Explication : Comme le montre la figure :
  • Le premier robot en position 0 se déplace dans le sens positif. Il sera réparé à la première usine.
  • Le deuxième robot en position 4 se déplace dans le sens négatif. Il sera réparé à la première usine.
  • Le troisième robot en position 6 sera réparé à la deuxième usine. Il n'a pas besoin de bouger.
  • La limite de la première usine est de 2, et elle a corrigé 2 robots.
  • La limite de la deuxième usine est de 2, et elle a corrigé 1 robot.
  • La distance totale est de |2 - 0| |2 - 4| |6 - 6| = 4. On peut montrer que nous ne pouvons pas atteindre une distance totale meilleure que 4.

Exemple 2 :

• Entrée : robot = [1,-1], usine = [[-2,1],[2,1]]
• Sortie : 2
• Explication : Comme le montre la figure :
  • Le premier robot en position 1 se déplace dans le sens positif. Il sera réparé à la deuxième usine.
  • Le deuxième robot en position -1 se déplace dans le sens négatif. Il sera réparé à la première usine.
  • La limite de la première usine est de 1, et elle a corrigé 1 robot.
  • La limite de la deuxième usine est de 1, et elle a corrigé 1 robot.
  • La distance totale est de |2 - 1| |(-2) - (-1)| = 2. On peut montrer que nous ne pouvons pas atteindre une distance totale meilleure que 2.

Contraintes :

• 1
• usine[j].length == 2
• -10⁹ 9
• 0 j
• L'entrée sera générée de telle sorte qu'il soit toujours possible de réparer chaque robot.

Indice :

1. Trier les robots et les usines selon leur position.
2. Après le tri, notez que chaque usine doit réparer certains sous-segments de robots.
3. Trouvez la distance totale minimale pour réparer les premiers i robots avec les premières j usines.

Solution :

Nous pouvons utiliser la programmation dynamique avec des tableaux de robots et d'usine triés. L’idée est de minimiser la distance que doit parcourir chaque robot pour être réparé par une usine, en respectant la capacité de réparation de chaque usine. Voici un aperçu étape par étape de l’approche :

1. Trier les tableaux du robot et de l'usine par position. Le tri aide à minimiser la distance de déplacement car nous pouvons affecter des robots à proximité aux usines à proximité.

2. Approche de programmation dynamique : Nous définissons une table DP 2D dp[i][j] où :

   • je représente les premiers robots i.
   • j représente les j premières usines.
   • dp[i][j] stocke la distance totale minimale pour réparer ces i robots à l'aide de ces j usines.

3. Transition d'État :

   • Pour chaque usine, essayez de réparer un sous-ensemble de robots consécutifs dans sa limite.
   • Pour une usine j à la position p, calculez la distance minimale requise pour lui affecter k robots en additionnant les distances de chaque robot à la position de l'usine.
   • Mettez à jour l'état du DP en sélectionnant le minimum entre réparer moins de robots ou utiliser au maximum la capacité de l'usine.

Implémentons cette solution en PHP : 2463. Distance totale minimale parcourue

<?php /**
 * @param Integer[] $robot
 * @param Integer[][] $factory
 * @return Integer
 */
function minimumTotalDistance($robot, $factory) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$robot = [0, 4, 6];
$factory = [[2, 2], [6, 2]];
echo minimumTotalDistance($robot, $factory);  // Output: 4

$robot = [1, -1];
$factory = [[-2, 1], [2, 1]];
echo minimumTotalDistance($robot, $factory);  // Output: 2
?>

Explication:

• Tri : Nous trions les robots et les usines par positions pour nous assurer d'attribuer les robots à proximité aux usines à proximité.
• Initialisation DP : Initialisez dp[0][0] = 0 car aucun robot réparé par aucune usine ne signifie une distance nulle.
• Transition de programmation dynamique :
  • Pour chaque usine j, nous essayons de réparer les k robots qui la précèdent dans sa limite.
  • La distance totale est accumulée dans sumDist.
  • Nous mettons à jour dp[i][j] avec la valeur minimale après avoir réparé k robots, en tenant compte de la distance et des états précédents.

Complexité

• Complexité temporelle : O(n * m * L) où n est le nombre de robots, m est le nombre d'usines et L est la limite maximale de réparations qu'une usine peut gérer.
• Complexité spatiale : O(n * m) pour la table DP.

Cette solution calcule efficacement la distance de déplacement minimale pour tous les robots à réparer dans les limites de leur usine.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

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!