最小移动总距离
难度:
标签:
题目描述
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 <= 100factory[j].length == 2-109 <= robot[i], positionj <= 1090 <= limitj <= robot.length- 测试数据保证所有机器人都可以被维修。
代码结果
运行时间: 410 ms, 内存: 20.1 MB
/*
思路：
1. 使用Stream对机器人位置和工厂进行排序。
2. 使用动态规划和Stream计算最小总移动距离。
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class SolutionStream {
public int minTotalDistance(int[] robot, int[][] factory) {
Arrays.sort(robot);
Arrays.sort(factory, (a, b) -> Integer.compare(a[0], b[0]));
int n = robot.length;
int m = factory.length;
int[][] dp = new int[m + 1][n + 1];
IntStream.rangeClosed(0, m).forEach(i -> Arrays.fill(dp[i], Integer.MAX_VALUE / 2));
dp[0][0] = 0;
IntStream.rangeClosed(1, m).forEach(i -> {
int pos = factory[i - 1][0];
int limit = factory[i - 1][1];
IntStream.rangeClosed(0, n).forEach(j -> {
dp[i][j] = dp[i - 1][j];
int[] dist = {0};
IntStream.rangeClosed(1, limit).forEach(k -> {
if (j >= k) {
dist[0] += Math.abs(robot[j - k] - pos);
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k] + dist[0]);
}
});
});
});
return dp[m][n];
}
}解释
方法:
这道题的解决方案利用动态规划来最小化所有机器人的总移动距离。首先，对机器人和工厂的位置进行排序，以便在动态规划过程中按顺序处理。定义一个辅助函数 get_min_move，它使用两个参数：当前考虑的工厂索引 idx 和剩余需要修理的机器人数量 left。通过使用递归和记忆化搜索来寻找将机器人指派给工厂的最优方案，以此减少机器人的总移动距离。在每个工厂处，函数尝试将尽可能多的机器人进行修理，同时也会探索不同的分配方式，以找出移动距离的最小可能值。
时间复杂度:
O(F * R * limit)
空间复杂度:
O(F * R)
代码细节讲解
🦆
在题解中，机器人和工厂位置排序的目的是什么？这种排序对算法的性能和结果有什么具体影响？
▷🦆
动态规划解法中为什么选择递归加记忆化搜索而不是迭代方法？记忆化搜索在这个问题中带来了哪些优势？
▷🦆
题解中提到的函数`get_min_move`的参数`left`代表什么？为何这一参数是关键在优化过程中？
▷