↓Skip to main content
  1. Posts/

LeetCode-2463 最小移动总距离

·1 min·
Table of Contents

LeetCode-2463 最小移动总距离 #

Solution 1 #

注意到如果出现两个机器人 “相遇” 的情况, 那么它们两两 “掉头” 显然是更优的. 另外, 可以发现两个同向的机器人交换目的地对结果没有影响. 第一点告诉我们, 最优的分配方法不会出现机器人 “相遇” 的情况, 可以理解为整个大区间划分成了一个个端点为工厂的小区间, 每个区间满足靠左的若干机器人向左 (目的地不一定是端点) , 其余机器人向右; 第二点告诉我们, 如果把视角转向工厂, 那么每个工厂实际上负责了一段子区间. 不妨假设 $robot$ 和 $factory$ 是按坐标轴从左向右排序的. 记 $dis[i][j]$ 为 $robot[0], \dots, robot[i]$ 由 $factory[0], \dots, factory[j]$ 进行维修时的最短总距离. 那么有 $$ dis[i][j] = \underset{0\leq k\leq limit_j}{min}{dis[i - k][j -1] + \sum_{t = i - k + 1}^{i}\vert robot[t] - factory[j] \vert} $$ 代码如下:

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        robot.sort()
        factory.sort()
        m, n = len(robot), len(factory)
        
        sum_dis = [[0 for i in range(n)] for j in range(m)]
        for j in range(n):
            cumulative_sum = 0
            for i in range(m):
                cumulative_sum += abs(factory[j][0] - robot[i])
                sum_dis[i][j] = cumulative_sum

        dis = [[int(1e12) for i in range(n)] for j in range(m)]
        for i in range(m):
            for j in range(n):
                for k in range(factory[j][1] + 1):
                    if i - k >= 0:
                        prev_dis = dis[i - k][j - 1] if j > 0 else int(1e12)
                        dis[i][j] =  min(dis[i][j],prev_dis + sum_dis[i][j] - sum_dis[i - k][j])
                    else:
                        dis[i][j] = min(dis[i][j], sum_dis[i][j])
                        break
        return dis[m - 1][n - 1]