最小移动总距离

标签: 数组 动态规划 排序

难度: Hard

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
  • -109 <= robot[i], positionj <= 109
  • 0 <= limitj <= robot.length
  • 测试数据保证所有机器人都可以被维修。

Submission

运行时间: 410 ms

内存: 20.1 MB

import math
from typing import List
from functools import lru_cache


class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        """

        :param robot:
        :param factory:
        :return:
        """
        robot.sort()
        factory.sort(key=lambda x: x[0])

        @lru_cache(None)
        def get_min_move(idx, left):
            if left == 0:
                return 0
            if idx == len(factory):
                if left == 0:
                    return 0
                return math.inf
            cur_buf = factory[idx][1]
            base = 0
            st_idx = len(robot) - left
            used = 0
            for i in range(min(cur_buf, left)):
                if robot[st_idx + i] >= factory[idx][0]:
                    break
                base += abs(robot[st_idx + i] - factory[idx][0])
                used += 1
            ret = base + get_min_move(idx + 1, left - used)
            r_start = len(robot) - (left - used)
            gap = 0
            for i in range(max(0, cur_buf - used)):
                if r_start + i >= len(robot):
                    break
                gap += abs(robot[r_start + i] - factory[idx][0])
                ret = min(ret, base + get_min_move(idx + 1, left - used - i - 1) + gap)
            return ret

        return get_min_move(0, len(robot))

Explain

这道题的解决方案利用动态规划来最小化所有机器人的总移动距离。首先，对机器人和工厂的位置进行排序，以便在动态规划过程中按顺序处理。定义一个辅助函数 get_min_move，它使用两个参数：当前考虑的工厂索引 idx 和剩余需要修理的机器人数量 left。通过使用递归和记忆化搜索来寻找将机器人指派给工厂的最优方案，以此减少机器人的总移动距离。在每个工厂处，函数尝试将尽可能多的机器人进行修理，同时也会探索不同的分配方式，以找出移动距离的最小可能值。

时间复杂度: O(F * R * limit)

空间复杂度: O(F * R)

import math
from typing import List
from functools import lru_cache


class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        # 对机器人和工厂的位置进行排序
        robot.sort()
        factory.sort(key=lambda x: x[0])

        # 使用递归和记忆化搜索以最小化移动距离
        @lru_cache(None)
        def get_min_move(idx, left):
            if left == 0:
                return 0
            if idx == len(factory):
                return math.inf
            cur_buf = factory[idx][1]
            base = 0
            st_idx = len(robot) - left
            used = 0
            # 为尽可能多的机器人分配当前工厂
            for i in range(min(cur_buf, left)):
                if robot[st_idx + i] >= factory[idx][0]:
                    break
                base += abs(robot[st_idx + i] - factory[idx][0])
                used += 1
            ret = base + get_min_move(idx + 1, left - used)
            r_start = len(robot) - (left - used)
            gap = 0
            for i in range(max(0, cur_buf - used)):
                if r_start + i >= len(robot):
                    break
                gap += abs(robot[r_start + i] - factory[idx][0])
                ret = min(ret, base + get_min_move(idx + 1, left - used - i - 1) + gap)
            return ret

        return get_min_move(0, len(robot))

Explore

在题解中，对机器人和工厂位置进行排序的目的是为了简化问题，使得在动态规划过程中可以按照一定的顺序来处理机器人和工厂的关系。通过排序，可以确保我们在考虑将机器人分配到工厂时，是按照位置的递增顺序进行的，这有助于减少不必要的重复计算。排序后的顺序可以提高算法效率，因为它使得我们能够按顺序逐步考虑最近的机器人和工厂匹配，从而在动态规划中更快地找到最小移动距离。此外，这种有序的处理方式也可以在实际操作中避免对所有可能的机器人和工厂组合进行全面的搜索，从而减少了算法的时间复杂性。

在这个问题中，选择递归加记忆化搜索而不是迭代方法的主要原因是问题的递归结构和状态转移方程的复杂性。递归方法可以更自然地模拟分配机器人到各个工厂的决策过程，并且可以通过记忆化来避免重复计算同一状态的结果，这样可以显著提高效率。记忆化搜索的优势在于它能够存储已经计算过的状态结果，避免在递归过程中对相同状态进行多次计算，从而减少计算量，加快求解速度。这在有大量状态需要重复访问的情况下特别有用，如本问题中的多种不同的机器人和工厂的分配方式。

函数`get_min_move`中的参数`left`代表剩余需要修理的机器人数量。这一参数是优化过程中的关键，因为它帮助函数追踪在当前状态下还有多少机器人需要被分配到工厂进行修理。通过知道剩余的机器人数量，函数可以决定是否继续尝试在当前工厂分配更多机器人或者移动到下一个工厂。此外，`left`参数的变化是确定递归结束条件的关键部分（即当没有剩余机器人需要修理时，递归结束），也是动态规划中用于判断何时更新状态和进行状态转移的重要因素。