T2463.最小移动总距离

dp, https://leetcode.cn/problems/minimum-total-distance-traveled/

X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 factory[j] = [positionj, limitj] ，表示第 j 个工厂的位置在 positionj ，且第 j 个工厂最多可以修理 limitj 个机器人。

每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置 。

所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。

任何时刻，你都可以设置部分机器人的移动方向。你的目标是最小化所有机器人总的移动距离。

请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。

注意：

所有机器人移动速度相同。
如果两个机器人移动方向相同，它们永远不会碰撞。
如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。
如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。
机器人从位置 x 到位置 y 的移动距离为 |y - x| 。

示例 1：

输入：robot = [0,4,6], factory = [[2,2],[6,2]]
输出：4
解释：如上图所示：
- 第一个机器人从位置 0 沿着正方向移动，在第一个工厂处维修。
- 第二个机器人从位置 4 沿着负方向移动，在第一个工厂处维修。
- 第三个机器人在位置 6 被第二个工厂维修，它不需要移动。
第一个工厂的维修上限是 2 ，它维修了 2 个机器人。
第二个工厂的维修上限是 2 ，它维修了 1 个机器人。
总移动距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4 。没有办法得到比 4 更少的总移动距离。

示例 2：

输入：robot = [1,-1], factory = [[-2,1],[2,1]]
输出：2
解释：如上图所示：
- 第一个机器人从位置 1 沿着正方向移动，在第二个工厂处维修。
- 第二个机器人在位置 -1 沿着负方向移动，在第一个工厂处维修。
第一个工厂的维修上限是 1 ，它维修了 1 个机器人。
第二个工厂的维修上限是 1 ，它维修了 1 个机器人。
总移动距离是 |2 - 1| + |(-2) - (-1)| = 2 。没有办法得到比 2 更少的总移动距离。

提示：

1 <= robot.length, factory.length <= 100
factory[j].length == 2
-10^9 <= robot[i], positionj <= 10^9
0 <= limitj <= robot.length
测试数据保证所有机器人都可以被维修。

这是一个经典的动态规划问题。为了使总移动距离最小，一个关键的观察是：如果我们将机器人和工厂都按照坐标从小到大排序，那么每个工厂修理的机器人一定是机器人序列中连续的一段。 换句话说，机器人的相对顺序在分配给工厂时不会发生“交叉”。

算法思路

排序：首先对机器人数组 robot 按坐标升序排序。对工厂数组 factory 按坐标升序排序。
状态定义：定义 dp[i][j] 表示前 i 个工厂修复前 j 个机器人的最小总距离。
状态转移：对于第 i 个工厂（坐标为 pos，容量为 limit），我们可以选择让它修理 k 个机器人，其中 $0 \leq k \leq min (j, l i m i t)$ 。如果该工厂修理最后 $k$ 个机器人（即索引从 $j - k$ 到 $j - 1$ 的机器人），则： $d p [i] [j] = min_{0 \leq k \leq min (j, l i m i t)} {d p [i - 1] [j - k] + \sum_{m = j - k}^{j - 1} | r o b o t [m] - p o s |}$
- 当 $k = 0$ 时，表示第 i 个工厂不修理任何机器人。
边界条件：
- dp[0][0] = 0：0个工厂修0个机器人，距离为0。
- dp[0][j] = infinity (当 $j > 0$ )：没有工厂无法修理机器人。
- dp[i][0] = 0：任何数量的工厂修理0个机器人，距离都为0。
复杂度分析：
- 时间复杂度： $O (M \cdot N^{2})$ ，其中 $M$ 是工厂数， $N$ 是机器人总数。在本题中 $M, N \leq 100$ ，计算量约为 $10^{6}$ ，在可接受范围内。
- 空间复杂度： $O (M \cdot N)$ ，可以通过滚动数组优化到 $O (N)$ 。

Python 代码实现

python

from typing import List

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        # 1. 排序
        robot.sort()
        factory.sort()
        
        n = len(robot)
        m = len(factory)
        
        # 2. DP 初始化
        # dp[i][j] 表示前 i 个工厂修理前 j 个机器人的最小距离
        # 初始化为一个足够大的数
        inf = float('inf')
        dp = [[inf] * (n + 1) for _ in range(m + 1)]
        
        # 边界：0个机器人距离永远是0
        for i in range(m + 1):
            dp[i][0] = 0
            
        # 3. 状态转移
        for i in range(1, m + 1):
            pos, limit = factory[i-1]
            for j in range(1, n + 1):
                # 情况1: 第 i 个工厂一个机器人都不修
                dp[i][j] = dp[i-1][j]
                
                # 情况2: 第 i 个工厂修理 k 个机器人 (1 <= k <= limit)
                cost = 0
                for k in range(1, min(j, limit) + 1):
                    # 累加第 j-k 个机器人到该工厂的距离
                    # 注意：robot 索引是从 0 开始的，所以是 j-k
                    cost += abs(robot[j-k] - pos)
                    if dp[i-1][j-k] != inf:
                        dp[i][j] = min(dp[i][j], dp[i-1][j-k] + cost)
                        
        return dp[m][n]

代码详解

外层循环 i：遍历每一个工厂。
中层循环 j：遍历当前考虑的机器人总数。
内层循环 k：尝试让当前第 i 个工厂修理 k 个机器人。
- 我们从第 j 个机器人（索引为 j-1）开始往前数 k 个。
- cost 变量实时累加这 k 个机器人到当前工厂位置 pos 的距离之和。
- dp[i-1][j-k] 是前 i-1 个工厂处理剩余机器人的最优解。
返回值：dp[m][n] 即为所有工厂处理完所有机器人的最小总距离。
该算法利用了排序后的性质，通过动态规划有效地在 $O (M \cdot N^{2})$ 时间内解决了分配问题。

T2463.最小移动总距离 ​

T2463.最小移动总距离