最小总行驶距离

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中文网其他相关文章！