最小總行駛距離

2463。最小總行駛距離

難度：難

主題：陣列、動態規劃、排序

X軸上有一些機器人和工廠。給定一個整數陣列機器人，其中 robots[i] 是第 i^th 個機器人的位置。您還得到一個2D 整數陣列工廠，其中factory[j] = [position_j, limit_j] 表示position_j 是j 的位置_第個工廠且第j_第個工廠最多可以維修_j個機器人。

每個機器人的位置都是獨一無二的。每個工廠的定位也獨一無二。請注意，機器人最初可以處於與工廠相同的位置。

所有機器人一開始都壞了；他們一直朝著一個方向前進。此方向可以是X軸的負方向或正方向。當機器人到達未達極限的工廠時，工廠會修理機器人，然後機器人就會停止移動。

隨時，您可以為某個機器人設定初始移動方向。您的目標是最小化所有機器人行駛的總距離。

返回所有機器人行駛的最小總距離。產生測試用例，以便可以修復所有機器人。

請注意

• 所有機器人以相同的速度移動。
• 如果兩個機器人朝同一方向移動，它們永遠不會碰撞。
• 如果兩個機器人向相反方向移動並且在某個時刻相遇，它們不會發生碰撞。他們互相交叉。
• 如果機器人經過一家達到極限的工廠，它就會穿過它，就好像它不存在一樣。
• 如果機器人從位置 x 移動到位置 y，則移動的距離為 |y - x|。

範例1：

• 輸入： 機器人 = [0,4,6]，工廠 = [[2,2],[6,2]]
• 輸出： 4
• 說明：如圖：
  • 位置 0 的第一個機器人朝正方向移動。會在第一工廠修復。
  • 位置 4 處的第二個機器人向負方向移動。會在第一工廠修復。
  • 6號位的第三台機器人將在第二工廠進行維修。它不需要移動。
  • 第一個工廠的限制是2個，固定了2個機器人。
  • 第二工廠限制為2個，固定了1個機器人。
  • 總距離為 |2 - 0| |2 - 4| |6 - 6| = 4. 可以證明我們無法得到比 4 更好的總距離。

範例2：

• 輸入： 機器人 = [1,-1], 工廠 = [[-2,1],[2,1]]
• 輸出： 2
• 說明：如圖：
  • 位置 1 的第一個機器人朝正方向移動。會在第二工廠修復。
  • 位置-1處的第二個機器人向負方向移動。會在第一工廠修復。
  • 第一個工廠的限制是1個，固定了1個機器人。
  • 第二工廠限制為1個，固定了1個機器人。
  • 總距離為 |2 - 1| |(-2) - (-1)| = 2. 可以證明我們無法得到比 2 更好的總距離。

約束：

• 1
• 工廠[j].length == 2
• -10⁹ 9
• 0 j
• 將產生輸入，以便始終可以修復每個機器人。

提示：

1. 按位置對機器人和工廠進行排序。
2. 排序後，注意每個工廠都應該修復部分機器人。
3. 找出修復前 j 個工廠的前 i 個機器人的最小總距離。

解：

我們可以對排序的機器人和工廠陣列使用動態程式設計。其想法是最大限度地縮短每個機器人到工廠維修所需的距離，同時尊重每個工廠的維修能力。以下是此方法的逐步細分：

1. 按位置對機器人和工廠數組進行排序。排序有助於最大限度地縮短行進距離，因為我們可以將附近的機器人分配到附近的工廠。

2. 動態規劃方法：我們定義一個2D DP表dp[i][j]，其中：

   • i 代表第 i 個機器人。
   • j代表前j個工廠。
   • dp[i][j] 儲存使用這 j 個工廠修復這 i 個機器人的最小總距離。

3. 態轉換:

   • 對於每個工廠，請嘗試在其限制內修復連續機器人的子集。
   • 對於位置 p 的工廠 j，透過將每個機器人到工廠位置的距離相加，計算為其分配 k 個機器人所需的最小距離。
   • 透過在修復較少的機器人或充分利用工廠產能之間選擇最小值來更新 DP 狀態。

讓我們用 PHP 實作這個解：2463。最小總行駛距離

<?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
?>

解釋：

• 排序：我們按位置對機器人和工廠進行排序，以確保將附近的機器人分配到附近的工廠。
• DP初始化：初始化dp[0][0] = 0，因為沒有工廠修理機器人意味著零距離。
• 動態規劃轉換：
  • 對於每個工廠j，我們嘗試在其限制範圍內修復其前面的k個機器人。
  • 總距離在 sumDist 累積。
  • 考慮到距離和之前的狀態，我們將 dp[i][j] 更新為修復 k 個機器人後的最小值。

複雜

• 時間複雜度：O(n * m * L)，其中n是機器人數量，m是工廠數量，L是任何工廠可以處理的最大維修限制。
• 空間複雜度：DP 表的 O(n * m)。

此解決方案可有效計算所有待維修機器人在工廠限制內的最小行進距離。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是最小總行駛距離的詳細內容。更多資訊請關注PHP中文網其他相關文章！