题目描述
leetcode 困难题
X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 factory[j] = [positionj, limitj] ，表示第 j 个工厂的位置在 positionj ，且第 j 个工厂最多可以修理 limitj 个机器人。
每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置 。
所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。
任何时刻，你都可以设置 部分 机器人的移动方向。你的目标是最小化所有机器人总的移动距离。
请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。
注意：
所有机器人移动速度相同。
如果两个机器人移动方向相同，它们永远不会碰撞。
如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。
如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。
机器人从位置 x 到位置 y 的移动距离为 |y - x| 。
示例1：
1
2
3
4
5
6
7
8
9
| 输入：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：
1
2
3
4
5
6
7
8
| 输入：robot = [1,-1], factory = [[-2,1],[2,1]]
输出：2
解释：如上图所示：
- 第一个机器人从位置 1 沿着正方向移动，在第二个工厂处维修。
- 第二个机器人在位置 -1 沿着负方向移动，在第一个工厂处维修。
第一个工厂的维修上限是 1 ，它维修了 1 个机器人。
第二个工厂的维修上限是 1 ，它维修了 1 个机器人。
总移动距离是 |2 - 1| + |(-2) - (-1)| = 2 。没有办法得到比 2 更少的总移动距离。
|
提示：
1
2
3
4
5
| 1 <= robot.length, factory.length <= 100
factory[j].length == 2
-109 <= robot[i], positionj <= 109
0 <= limitj <= robot.length
测试数据保证所有机器人都可以被维修。
|
分析
有一个关键的结论：
设两个机器人的位置分别为 r1, r2，且 r1 < r2 ，机器人去的工厂的位置为 f1,f2 ，则 f1 必然小于 f2 ，因为如果 f1 > f2 的话，交换这两个机器人去的工厂，移动距离就变小了。
因此我们可以先对机器人和工厂按照位置从小到大排序，那么每个工厂要修复的机器人就将是连续的一段。
在以下几种解法中，我们统一设 f(i, j) 的含义为第 j 个及其右侧的工厂，修理第 i 个及其右侧的机器人时的最小距离，那么 f(0, 0) 就是题目所求。
记忆化搜索
一种解法是递归 + 记忆化搜索。
对于某个 f(i, j)，我们枚举出第 j 个工厂修任意个机器人的可能（比如修 k 个），同时设修这 k 个机器人所花费的距离为 d(k)，那么只需要取所有 f(i + k + 1, j + 1) + d(k) 的最小值，就是我们要求的 f(i, j)。
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
| class Solution {
long[][] cache;
List<Integer> robot;
int[][] factory;
public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
Collections.sort(robot);
Arrays.sort(factory, (a, b) -> a[0] - b[0]);
this.robot = robot;
this.factory = factory;
this.cache = new long[robot.size()][factory.length];
return dfs(0, 0);
}
private long dfs(int i, int j){
if(i >= robot.size()){
return 0;
}
if(j >= factory.length){
return Long.MAX_VALUE;
}
if(cache[i][j] != 0){
return cache[i][j];
}
long min = dfs(i, j + 1);
long d = 0;
for(int k = 0; k < factory[j][1] && i + k < robot.size(); k++){
d += Math.abs(robot.get(i + k) - factory[j][0]);
long temp = dfs(i + k + 1, j + 1);
long next = temp == Long.MAX_VALUE ? Long.MAX_VALUE : temp + d;
min = Math.min(min, next);
}
cache[i][j] = min;
return min;
}
}
|
dp
根据 记忆化搜索 的解法，我们容易发现前面工厂的状态总是依赖于后面工厂的状态，所以我们只需要逆序遍历 factory 就可以实现动态规划，简略的方程如下：
f(i, j) = min( f(i + k + 1, j + 1) + d(k) ) （ k 取值范围为 [0, factory[i][1]] - 1）
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
| class Solution {
public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
Collections.sort(robot);
Arrays.sort(factory, (a, b) -> a[0] - b[0]);
int rs = robot.size(), fs = factory.length;
long[][] dp = new long[rs][fs + 1];
IntStream.range(0, dp.length).forEach(index -> Arrays.fill(dp[index], Long.MAX_VALUE));
for(int j = fs - 1; j >= 0; j--){
for(int i = 0; i < rs; i++){
long min = dp[i][j + 1];
long d = 0;
for(int k = 0; k <= factory[j][1] - 1 && i + k < rs; k++){
d += Math.abs(robot.get(i + k) - factory[j][0]);
long next = i + k == rs - 1 ? 0 : dp[i + k + 1][j + 1] ;
if(next != Long.MAX_VALUE){
min = Math.min(min, next + d);
}
}
dp[i][j] = min;
}
}
return dp[0][0];
}
}
|
滚动数组
就像背包问题一样，我们可以发现工厂 j 只会依赖于工厂 j + 1 的状态，即实际上我们只需要保留最新的工厂状态，可以利用滚动数组进行优化。
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
| class Solution {
public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
Collections.sort(robot);
Arrays.sort(factory, (a, b) -> a[0] - b[0]);
int rs = robot.size(), fs = factory.length;
long[] dp = new long[rs + 1];
Arrays.fill(dp, Long.MAX_VALUE);
dp[rs] = 0;
for(int j = fs - 1; j >= 0; j--){
for(int i = 0; i < rs; i++){
long min = dp[i];
long d = 0;
for(int k = 0; k <= factory[j][1] - 1 && i + k < rs; k++){
d += Math.abs(robot.get(i + k) - factory[j][0]);
long next = dp[i + k + 1];
if(next != Long.MAX_VALUE){
min = Math.min(min, next + d);
}
}
dp[i] = min;
}
}
return dp[0];
}
}
|