Minimale zurückgelegte Gesamtstrecke

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!