2463。最小總行駛距離

難度：難

主題：數(shù)組、動(dòng)態(tài)規(guī)劃、排序

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

每個(gè)機(jī)器人的位置都是獨(dú)一無二的。每個(gè)工廠的定位也獨(dú)一無二。請(qǐng)注意，機(jī)器人最初可以處于與工廠相同的位置。

所有機(jī)器人一開始都?jí)牧?；他們一直朝著一個(gè)方向前進(jìn)。該方向可以是X軸的負(fù)方向或正方向。當(dāng)機(jī)器人到達(dá)未達(dá)到極限的工廠時(shí)，工廠會(huì)修理機(jī)器人，然后機(jī)器人就會(huì)停止移動(dòng)。

隨時(shí)，您可以為某個(gè)機(jī)器人設(shè)置初始移動(dòng)方向。您的目標(biāo)是最小化所有機(jī)器人行駛的總距離。

返回所有機(jī)器人行駛的最小總距離。生成測(cè)試用例，以便可以修復(fù)所有機(jī)器人。

請(qǐng)注意

• 所有機(jī)器人以相同的速度移動(dòng)。
• 如果兩個(gè)機(jī)器人朝同一方向移動(dòng)，它們永遠(yuǎn)不會(huì)碰撞。
• 如果兩個(gè)機(jī)器人向相反方向移動(dòng)并且在某個(gè)時(shí)刻相遇，它們不會(huì)發(fā)生碰撞。他們互相交叉。
• 如果機(jī)器人經(jīng)過一家達(dá)到極限的工廠，它就會(huì)穿過它，就好像它不存在一樣。
• 如果機(jī)器人從位置 x 移動(dòng)到位置 y，則移動(dòng)的距離為 |y - x|。

示例1：

• 輸入： 機(jī)器人 = [0,4,6]，工廠 = [[2,2],[6,2]]
• 輸出： 4
• 說明：如圖：
  • 位置 0 的第一個(gè)機(jī)器人向正方向移動(dòng)。會(huì)在第一工廠修復(fù)。
  • 位置 4 處的第二個(gè)機(jī)器人向負(fù)方向移動(dòng)。會(huì)在第一工廠修復(fù)。
  • 6號(hào)位的第三臺(tái)機(jī)器人將在第二工廠進(jìn)行維修。它不需要移動(dòng)。
  • 第一個(gè)工廠的限制是2個(gè)，固定了2個(gè)機(jī)器人。
  • 第二工廠限制為2個(gè)，固定了1個(gè)機(jī)器人。
  • 總距離為 |2 - 0| |2 - 4| |6 - 6| = 4. 可以證明我們無法獲得比 4 更好的總距離。

示例2：

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

約束：

• 1
• 工廠[j].length == 2
• -10⁹ 9
• 0 j
• 將生成輸入，以便始終可以修復(fù)每個(gè)機(jī)器人。

提示：

1. 按位置對(duì)機(jī)器人和工廠進(jìn)行排序。
2. 排序后，注意每個(gè)工廠都應(yīng)該修復(fù)部分機(jī)器人。
3. 找到修復(fù)前 j 個(gè)工廠的前 i 個(gè)機(jī)器人的最小總距離。

解決方案：

我們可以對(duì)排序的機(jī)器人和工廠數(shù)組使用動(dòng)態(tài)編程。其想法是最大限度地縮短每個(gè)機(jī)器人到工廠維修所需的距離，同時(shí)尊重每個(gè)工廠的維修能力。以下是該方法的逐步細(xì)分：

1. 按位置對(duì)機(jī)器人和工廠數(shù)組進(jìn)行排序。排序有助于最大限度地縮短行進(jìn)距離，因?yàn)槲覀兛梢詫⒏浇臋C(jī)器人分配到附近的工廠。

2. 動(dòng)態(tài)規(guī)劃方法：我們定義一個(gè)2D DP表dp[i][j]，其中：

   • i 代表第 i 個(gè)機(jī)器人。
   • j代表前j個(gè)工廠。
   • dp[i][j] 存儲(chǔ)使用這 j 個(gè)工廠修復(fù)這 i 個(gè)機(jī)器人的最小總距離。

3. 狀態(tài)轉(zhuǎn)換:

   • 對(duì)于每個(gè)工廠，嘗試在其限制內(nèi)修復(fù)連續(xù)機(jī)器人的子集。
   • 對(duì)于位置 p 的工廠 j，通過將每個(gè)機(jī)器人到工廠位置的距離相加，計(jì)算為其分配 k 個(gè)機(jī)器人所需的最小距離。
   • 通過在修復(fù)更少的機(jī)器人或充分利用工廠產(chǎn)能之間選擇最小值來更新 DP 狀態(tài)。

讓我們用 PHP 實(shí)現(xiàn)這個(gè)解決方案：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
?>

解釋：

• 排序：我們按位置對(duì)機(jī)器人和工廠進(jìn)行排序，以確保將附近的機(jī)器人分配到附近的工廠。
• DP初始化：初始化dp[0][0] = 0，因?yàn)闆]有工廠修理機(jī)器人意味著零距離。
• 動(dòng)態(tài)規(guī)劃轉(zhuǎn)換：
  • 對(duì)于每個(gè)工廠j，我們嘗試在其限制范圍內(nèi)修復(fù)其前面的k個(gè)機(jī)器人。
  • 總距離在 sumDist 中累積。
  • 考慮到距離和之前的狀態(tài)，我們將 dp[i][j] 更新為修復(fù) k 個(gè)機(jī)器人后的最小值。

復(fù)雜

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

該解決方案可有效計(jì)算所有待維修機(jī)器人在工廠限制內(nèi)的最小行進(jìn)距離。

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請(qǐng)考慮在 GitHub 上給 存儲(chǔ)庫(kù) 一個(gè)星號(hào)或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？。您的支持對(duì)我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請(qǐng)隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

以上是最小總行駛距離的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！