2463-最小移动总距离

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

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
  • 测试数据保证所有机器人都可以被维修。

视频讲解 已出炉，重点分析了记忆化搜索与递推的优缺点，以及为什么空间压缩要倒序遍历。

欢迎点赞三连，在评论区分享你对这场周赛的看法~

方法一：记忆化搜索

用邻项交换法可以证明，对机器人和工厂按照位置从小到大排序，那么每个工厂修复的机器人就是连续的一段了。

定义 f(i,j) 表示用第 i 个及其右侧的工厂，修理第 j 个及其右侧的机器人，机器人移动的最小总距离。

枚举第 i 个工厂修了 k 个机器人，则有 f(i,j) = \min\limits_{k}^{}{f(i+1,j+k) + \text{cost}(i,j,k)。

这里 cost}(i,j,k) 表示第 i 个工厂修复从 j 到 j+k-1 的机器人，移动距离就是这些机器人到第 i 个工厂的距离之和。

注意 k\le\textit{limit}[i]。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        factory.sort(key=lambda f: f[0])
        robot.sort()
        n, m = len(factory), len(robot)
        @cache
        def f(i: int, j: int) -> int:
            if j == m: return 0
            if i == n - 1:
                if m - j > factory[i][1]: return inf
                return sum(abs(x - factory[i][0]) for x in robot[j:])
            res = f(i + 1, j)
            s, k = 0, 1
            while k <= factory[i][1] and j + k - 1 < m:
                s += abs(robot[j + k - 1] - factory[i][0])
                res = min(res, s + f(i + 1, j + k))
                k += 1
            return res
        return f(0, 0)
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
func minimumTotalDistance(robot []int, factory [][]int) int64 {
	sort.Slice(factory, func(i, j int) bool { return factory[i][0] < factory[j][0] })
	sort.Ints(robot)
	n, m := len(factory), len(robot)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, m)
		for j := range dp[i] {
			dp[i][j] = -1
		}
	}
	var f func(int, int) int
	f = func(i, j int) (res int) {
		if j >= m {
			return
		}
		dv := &dp[i][j]
		if *dv != -1 {
			return *dv
		}
		defer func() { *dv = res }()
		if i == n-1 {
			if m-j > factory[i][1] {
				return 1e18
			}
			for _, x := range robot[j:] {
				res += abs(x - factory[i][0])
			}
			return
		}
		res = f(i+1, j)
		for s, k := 0, 1; k <= factory[i][1] && j+k-1 < m; k++ {
			s += abs(robot[j+k-1] - factory[i][0])
			res = min(res, s+f(i+1, j+k))
		}
		return
	}
	return int64(f(0, 0))
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

复杂度分析

  • 时间复杂度：O(nm^2)，其中 n 为 factory 的长度，m 为 robot 的长度。
  • 空间复杂度：O(nm)。

方法二：递推

根据方法一，排序后，定义 f[i][j] 表示前 i 个工厂修复前 j 个机器人的最小移动总距离。

枚举第 i 个工厂修了 k 个机器人，则有

f[i][j] = \min\limits_{k=0}^{\min(j, \textit{limit}[i])} f[i-1][j-k] + \sum_{p=j-k+1}^{j} |\textit{robot}[p]-\textit{position}[i]|

代码实现时，第一个维度可以像 01 背包那样优化掉。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        factory.sort(key=lambda f: f[0])
        robot.sort()
        m = len(robot)
        f = [0] + [inf] * m
        for pos, limit in factory:
            for j in range(m, 0, -1):
                cost = 0
                for k in range(1, min(j, limit) + 1):
                    cost += abs(robot[j - k] - pos)
                    f[j] = min(f[j], f[j - k] + cost)
        return f[m]
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
        Arrays.sort(factory, (a, b) -> a[0] - b[0]);
        var r = robot.stream().mapToInt(i -> i).toArray();
        Arrays.sort(r);
        var m = r.length;
        var f = new long[m + 1];
        Arrays.fill(f, (long) 1e18);
        f[0] = 0;
        for (var fa : factory)
            for (var j = m; j > 0; j--) {
                var cost = 0L;
                for (var k = 1; k <= Math.min(j, fa[1]); ++k) {
                    cost += Math.abs(r[j - k] - fa[0]);
                    f[j] = Math.min(f[j], f[j - k] + cost);
                }
            }
        return f[m];
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    long long minimumTotalDistance(vector<int> &robot, vector<vector<int>> &factory) {
        sort(factory.begin(), factory.end(), [](auto &a, auto &b) { return a[0] < b[0]; });
        sort(robot.begin(), robot.end());
        int m = robot.size();
        long f[m + 1]; memset(f, 0x3f, sizeof(f));
        f[0] = 0;
        for (auto &fa: factory)
            for (int j = m; j > 0; j--) {
                long cost = 0L;
                for (int k = 1; k <= min(j, fa[1]); ++k) {
                    cost += abs(robot[j - k] - fa[0]);
                    f[j] = min(f[j], f[j - k] + cost);
                }
            }
        return f[m];
    }
};
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func minimumTotalDistance(robot []int, factory [][]int) int64 {
	sort.Slice(factory, func(i, j int) bool { return factory[i][0] < factory[j][0] })
	sort.Ints(robot)
	m := len(robot)
	f := make([]int, m+1)
	for i := range f {
		f[i] = 1e18
	}
	f[0] = 0
	for _, fa := range factory {
		for j := m; j > 0; j-- {
			for k, cost := 1, 0; k <= min(j, fa[1]); k++ {
				cost += abs(robot[j-k] - fa[0])
				f[j] = min(f[j], f[j-k]+cost)
			}
		}
	}
	return int64(f[m])
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

复杂度分析

  • 时间复杂度：O(nm^2)，其中 n 为 factory 的长度，m 为 robot 的长度。
  • 空间复杂度：O(m)。

相似题目

 Comments
On this page
2463-最小移动总距离
  1. 方法一：记忆化搜索
  2. 方法二：递推