Hard

题目描述

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

每个机器人的位置都是唯一的。每个工厂的位置也都是唯一的。注意机器人可以和工厂在同一个位置。

所有机器人最初都是损坏的；它们会朝一个方向移动。方向可以是 X 轴的负方向或正方向。当一个机器人到达一个没有达到其修理上限的工厂时，工厂会修理该机器人，机器人停止移动。

在任何时刻，你可以设置某个机器人的初始移动方向。你的目标是最小化所有机器人行进的总距离。

返回所有机器人行进的最小总距离。测试用例保证所有机器人都可以被修理。

注意：

  • 所有机器人以相同速度移动
  • 如果两个机器人朝同一方向移动，它们永远不会碰撞
  • 如果两个机器人朝相反方向移动并在某点相遇，它们不会碰撞，而是相互穿过
  • 如果机器人经过一个已达修理上限的工厂，它会穿过该工厂，就像工厂不存在一样
  • 如果机器人从位置 x 移动到位置 y，它移动的距离是 |y - x|

示例 1：

输入：robot = [0,4,6], factory = [[2,2],[6,2]]
输出：4
解释：
- 位置 0 的第一个机器人向正方向移动，在第一个工厂修理
- 位置 4 的第二个机器人向负方向移动，在第一个工厂修理  
- 位置 6 的第三个机器人在第二个工厂修理，不需要移动
总距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4

示例 2：

输入：robot = [1,-1], factory = [[-2,1],[2,1]]
输出：2

提示：

  • 1 <= robot.length, factory.length <= 100
  • factory[j].length == 2
  • -10^9 <= robot[i], positionj <= 10^9
  • 0 <= limitj <= robot.length
  • 输入保证总是可以修理每个机器人

解题思路

这道题可以用动态规划来解决。核心思路是：

  1. 排序：首先对机器人和工厂按位置排序。排序后，最优解中每个工厂修理的机器人必定是连续的一段。

  2. 状态定义：dp[i][j] 表示前 i 个机器人使用前 j 个工厂修理的最小总距离。

  3. 状态转移：对于第 j 个工厂，我们需要决定让它修理哪些机器人。假设第 j 个工厂修理机器人 k 到 i-1（0-indexed），那么：

    dp[i][j] = min(dp[k][j-1] + cost(k, i-1, j))

    其中 cost(k, i-1, j) 是让第 j 个工厂修理机器人 k 到 i-1 的总距离。

  4. 边界条件：

    • dp[0][j] = 0（0个机器人需要0距离）
    • dp[i][0] = INF（没有工厂无法修理机器人）

  5. 优化：由于工厂有修理数量限制，在状态转移时需要确保第 j 个工厂修理的机器人数量不超过其限制。

为了处理工厂的数量限制，我们可以将每个工厂按其限制展开为多个位置相同但限制为1的工厂，这样简化了DP的实现。

时间复杂度为 O(m×n²)，其中 m 是机器人数量，n 是展开后的工厂数量。

代码实现

class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end());
        
        // 展开工厂，每个工厂按其限制数量展开
        vector<int> factories;
        for (auto& f : factory) {
            for (int i = 0; i < f[1]; i++) {
                factories.push_back(f[0]);
            }
        }
        
        int m = robot.size(), n = factories.size();
        // dp[i][j] 表示前i个机器人用前j个工厂修理的最小距离
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 1e18));
        
        // 初始化：0个机器人需要0距离
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 0;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 第j个工厂不修理第i个机器人
                dp[i][j] = dp[i][j-1];
                // 第j个工厂修理第i个机器人
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + abs(robot[i-1] - factories[j-1]));
            }
        }
        
        return dp[m][n];
    }
};

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        robot.sort()
        factory.sort()
        
        # 展开工厂，每个工厂按其限制数量展开
        factories = []
        for pos, limit in factory:
            factories.extend([pos] * limit)
        
        m, n = len(robot), len(factories)
        # dp[i][j] 表示前i个机器人用前j个工厂修理的最小距离
        dp = [[float('inf')] * (n + 1) for _ in range(m + 1)]
        
        # 初始化：0个机器人需要0距离
        for j in range(n + 1):
            dp[0][j] = 0
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # 第j个工厂不修理第i个机器人
                dp[i][j] = dp[i][j-1]
                # 第j个工厂修理第i个机器人
                dp[i][j] = min(dp[i][j], dp[i-1][j-1] + abs(robot[i-1] - factories[j-1]))
        
        return dp[m][n]

public class Solution {
    public long MinimumTotalDistance(IList<int> robot, int[][] factory) {
        var robotList = robot.ToList();
        robotList.Sort();
        Array.Sort(factory, (a, b) => a[0].CompareTo(b[0]));
        
        // 展开工厂，每个工厂按其限制数量展开
        var factories = new List<int>();
        foreach (var f in factory) {
            for (int i = 0; i < f[1]; i++) {
                factories.Add(f[0]);
            }
        }
        
        int m = robotList.Count, n = factories.Count;
        // dp[i][j] 表示前i个机器人用前j个工厂修理的最小距离
        var dp = new long[m + 1][];
        for (int i = 0; i <= m; i++) {
            dp[i] = new long[n + 1];
            Array.Fill(dp[i], long.MaxValue / 2);
        }
        
        // 初始化：0个机器人需要0距离
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 0;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 第j个工厂不修理第i个机器人
                dp[i][j] = dp[i][j-1];
                // 第j个工厂修理第i个机器人
                dp[i][j] = Math.Min(dp[i][j], dp[i-1][j-1] + Math.Abs(robotList[i-1] - factories[j-1]));
            }
        }
        
        return dp[m][n];
    }
}

var minimumTotalDistance = function(robot, factory) {
    robot.sort((a, b) => a - b);
    factory.sort((a, b) => a[0] - b[0]);
    
    // 展开工厂，每个工厂按其限制数量展开
    const factories = [];
    for (const [pos, limit] of factory) {
        for (let i = 0; i < limit; i++) {
            factories.push(pos);
        }
    }
    
    const m = robot.length, n = factories.length;
    // dp[i][j] 表示前i个机器人用前j个工厂修理的最小距离
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(Infinity));
    
    // 初始化：0个机器人需要0距离
    for (let j = 0; j <= n; j++) {
        dp[0][j] = 0;
    }
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // 第j个工厂不修理第i个机器人
            dp[i][j] = dp[i][j-1];
            // 第j个工厂修理第i个机器人
            dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1] + Math.abs(robot[i-1] - factories[j-1]));
        }
    }
    
    return dp[m][n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型说明
时间复杂度O(m × n)，其中 m 是机器人数量，n 是展开后的工厂数量（最多为机器人数量的总和）
空间复杂度O(m × n)，用于存储 DP 表

相关题目