2463. Minimale zurückgelegte Gesamtstrecke

Schwierigkeit:Schwer

Themen:Array, dynamische Programmierung, Sortieren

Auf der X-Achse befinden sich einige Roboter und Fabriken. Sie erhalten ein ganzzahliges Array robot, wobei robot[i] die Position des i^ten Roboters ist. Sie erhalten au?erdem eine 2D-Integer-Array-Factory, wobei ?factory[j] = [position_j, limit_j]“ angibt, dass position_j die Position von j ist _te Fabrik und dass die j_te Fabrik maximal _j Roboter reparieren kann.

Die Positionen jedes Roboters sind einzigartig. Auch die Positionen jeder Fabrik sind einzigartig. Beachten Sie, dass sich ein Roboter zun?chst in der gleichen Position wie eine Fabrik befinden kann.

Alle Roboter sind zun?chst kaputt; sie bewegen sich weiter in eine Richtung. Die Richtung kann die negative oder positive Richtung der X-Achse sein. Wenn ein Roboter eine Fabrik erreicht, die ihr Limit nicht erreicht hat, repariert die Fabrik den Roboter und er h?rt auf, sich zu bewegen.

Sie k?nnen jederzeit die anf?ngliche Bewegungsrichtung für einige Roboter festlegen. Ihr Ziel ist es, die von allen Robotern zurückgelegte Gesamtstrecke zu minimieren.

Gib die minimale Gesamtstrecke zurück, die von allen Robotern zurückgelegt wurde. Die Testf?lle werden so generiert, dass alle Roboter repariert werden k?nnen.

Beachten Sie, dass

• Alle Roboter bewegen sich mit der gleichen Geschwindigkeit.
• Wenn sich zwei Roboter in die gleiche Richtung bewegen, werden sie niemals kollidieren.
• Wenn sich zwei Roboter in entgegengesetzte Richtungen bewegen und sich irgendwann treffen, kollidieren sie nicht. Sie kreuzen sich.
• Wenn ein Roboter an einer Fabrik vorbeikommt, die ihre Grenzen erreicht hat, überquert er sie, als ob sie nicht existierte.
• Wenn sich der Roboter von einer Position x zu einer Position y bewegt hat, ist die Distanz, die er zurückgelegt hat, |y - x|.

Beispiel 1:

• Eingabe: Roboter = [0,4,6], Fabrik = [[2,2],[6,2]]
• Ausgabe: 4
• Erkl?rung: Wie in der Abbildung gezeigt:
  • Der erste Roboter an Position 0 bewegt sich in die positive Richtung. Die Reparatur erfolgt im ersten Werk.
  • Der zweite Roboter an Position 4 bewegt sich in die negative Richtung. Die Reparatur erfolgt im ersten Werk.
  • Der dritte Roboter an Position 6 wird in der zweiten Fabrik repariert. Es muss nicht bewegt werden.
  • Das Limit der ersten Fabrik betr?gt 2 und es wurden 2 Roboter repariert.
  • Das Limit der zweiten Fabrik betr?gt 2 und es wurde 1 Roboter repariert.
  • Die Gesamtstrecke betr?gt |2 - 0| |2 - 4| |6 - 6| = 4. Es l?sst sich zeigen, dass wir keine bessere Gesamtdistanz als 4 erreichen k?nnen.

Beispiel 2:

• Eingabe: Roboter = [1,-1], Fabrik = [[-2,1],[2,1]]
• Ausgabe: 2
• Erkl?rung: Wie in der Abbildung gezeigt:
  • Der erste Roboter an Position 1 bewegt sich in die positive Richtung. Die Reparatur erfolgt in der zweiten Fabrik.
  • Der zweite Roboter an Position -1 bewegt sich in die negative Richtung. Die Reparatur erfolgt im ersten Werk.
  • Das Limit der ersten Fabrik betr?gt 1 und es wurde 1 Roboter repariert.
  • Das Limit der zweiten Fabrik betr?gt 1 und es wurde 1 Roboter repariert.
  • Die Gesamtstrecke betr?gt |2 - 1| |(-2) - (-1)| = 2. Es l?sst sich zeigen, dass wir keine bessere Gesamtdistanz als 2 erreichen k?nnen.

Einschr?nkungen:

• 1 <= robot.length, Factory.length <= 100
• factory[j].length == 2
• -10⁹ <= robot[i], positionj <= 10⁹
• 0 <= limit_j <= robot.length
• Die Eingabe wird so generiert, dass es immer m?glich ist, jeden Roboter zu reparieren.

Hinweis:

1. Sortieren Sie Roboter und Fabriken nach ihrer Position.
2. Beachten Sie nach dem Sortieren, dass jede Fabrik ein Untersegment von Robotern reparieren sollte.
3. Ermitteln Sie die minimale Gesamtentfernung, um First-i-Roboter mit First-j-Fabriken zu reparieren.

L?sung:

Wir k?nnen dynamische Programmierung mit sortierten Roboter- und Fabrikarrays verwenden. Die Idee besteht darin, die Distanz zu minimieren, die jeder Roboter zurücklegen muss, um von einer Fabrik repariert zu werden, und dabei die Reparaturkapazit?t jeder Fabrik zu respektieren. Hier ist eine schrittweise Aufschlüsselung des Ansatzes:

1. Sortieren Sie die Roboter- und Fabrikarrays nach Position. Die Sortierung tr?gt dazu bei, die Reisedistanz zu minimieren, da wir nahegelegene Roboter nahegelegenen Fabriken zuordnen k?nnen.

2. Dynamischer Programmieransatz: Wir definieren eine 2D-DP-Tabelle dp[i][j], wobei:

   • i repr?sentiert die ersten i-Roboter.
   • j repr?sentiert die ersten j-Fabriken.
   • dp[i][j] speichert die minimale Gesamtentfernung für die Reparatur dieser i-Roboter mithilfe dieser j-Fabriken.

3. Zustandsübergang:

   • Versuchen Sie für jede Fabrik, eine Teilmenge aufeinanderfolgender Roboter innerhalb ihres Limits zu reparieren.
   • Berechnen Sie für eine Fabrik j an Position p den Mindestabstand, der erforderlich ist, um ihr k Roboter zuzuweisen, indem Sie die Abst?nde von jedem Roboter zur Fabrikposition summieren.
   • Aktualisieren Sie den DP-Status, indem Sie das Minimum zwischen der Reparatur weniger Roboter oder der vollst?ndigen Nutzung der Fabrikkapazit?t ausw?hlen.

Lassen Sie uns diese L?sung in PHP implementieren: 2463. Minimale zurückgelegte Gesamtstrecke

  
  
  Erl?uterung:




Sortierung: Wir sortieren Roboter und Fabrik nach Positionen, um sicherzustellen, dass wir nahegelegene Roboter den nahegelegenen Fabriken zuordnen.

DP-Initialisierung: Initialisieren Sie dp[0][0] = 0, da keine von Fabriken reparierten Roboter eine Entfernung von Null bedeuten.

Dynamischer Programmierübergang:


Für jede Fabrik j versuchen wir, die k Roboter davor innerhalb ihres Limits zu reparieren.
Die Gesamtdistanz wird in sumDist akkumuliert.
Wir aktualisieren dp[i][j] mit dem Mindestwert nach der Reparatur von k Robotern unter Berücksichtigung der Entfernung und der vorherigen Zust?nde.








  
  
  Komplexit?t




Zeitkomplexit?t: O(n * m * L) wobei n die Anzahl der Roboter, m die Anzahl der Fabriken und L die maximale Reparaturgrenze ist, die jede Fabrik bew?ltigen kann.

Raumkomplexit?t: O(n * m) für die DP-Tabelle.


Diese L?sung berechnet effizient die Mindestfahrstrecke für alle zu reparierenden Roboter innerhalb ihrer Werksgrenzen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonMinimale zurückgelegte Gesamtstrecke. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!