2023-05-06：X 轴上有一些机器人和工厂。给你一个整数数组 robot，其中 robot[i]是第 i 个机器人的位置
再给你一个二维整数数组 factory，其中 factory[j] = [positionj, limitj]
表示第 j 个工厂的位置在 positionj ，且第 j 个工厂最多可以修理 limitj 个机器人
每个机器人所在的位置 互不相同。每个工厂所在的位置也互不相同
注意一个机器人可能一开始跟一个工厂在相同的位置
所有机器人一开始都是坏的，他们会沿着设定的方向一直移动
设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向
当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动
任何时刻，你都可以设置 部分 机器人的移动方向
你的目标是最小化所有机器人总的移动距离
请你返回所有机器人移动的最小总距离
注意：
所有机器人移动速度相同
如果两个机器人移动方向相同，它们永远不会碰撞
如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过
如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动
机器人从位置 x 到位置 y 的移动距离为 |y - x|
1 <= robot.length, factory.length <= 100
factory[j].length == 2
-10 ^ 9 <= robot[i], positionj <= 10 ^ 9
0 <= limitj <= robot.length
测试数据保证所有机器人都可以被维修。
输入：robot = [0,4,6], factory = [[2,2],[6,2]]。
输出：4。
答案 2023-05-06：
算法 1：
1.首先对机器人位置数组 robot 进行排序，按照从小到大的顺序排列。
2.对工厂位置数组 factory 按照第一个元素排序，也就是按照工厂所在的位置从小到大排列。
3.创建一个二维数组 dp，大小为 (n, m)，其中 n 是机器人个数，m 是工厂个数。初始时，所有元素置为 -1。
4.调用递归函数 process1(robot, factory, n-1, m-1, dp) 计算最小总距离。
--1.如果机器人已经全部处理完毕（即 i < 0），返回 0。
--2.如果已经没有可用的工厂（即 j < 0），返回最大整数值（表示当前状态不合法，无解）。
--3.如果 dp[i][j] 已经计算过了，直接返回这个值。
--4 定义变量 ans 表示当前状态下的最小距离，初始化为左边一个工厂的最小距离。然后遍历当前工厂能够维修的机器人，计算这些机器人到当前工厂的距离，并且调用递归函数 process1 计算剩余机器人和工厂的最小距离。
--5.在所有可能的状态中选择一个距离最小的状态，并返回这个距离。
5.返回递归函数 process1 的计算结果。
时间复杂度：O((n ^ m)m)，其中 n 是机器人个数，m 是工厂个数。
空间复杂度：O(nm)。
算法 2：
1.首先对机器人位置数组 robot 进行排序，按照从小到大的顺序排列。
2.对工厂位置数组 factory 按照第一个元素排序，也就是按照工厂所在的位置从小到大排列。
3.创建一个二维数组 dp，大小为 (n, m)，其中 n 是机器人个数，m 是工厂个数。初始时，所有元素置为最大整数值。
4.遍历机器人和工厂，使用动态规划计算最小总距离。
--1.定义变量 ans 表示当前状态下的最小距离，初始化为左边一个工厂的最小距离。
--2.定义变量 distance 表示当前机器人到当前工厂的距离，初始化为 0。
--3.遍历当前工厂能够维修的机器人，计算这些机器人到当前工厂的距离，并且查找剩余机器人和工厂的最小距离。
--4.更新变量 ans 和 distance。
--5.在所有可能的状态中选择一个距离最小的状态，并将这个距离赋值给当前状态。
5.返回 dp[n-1][m-1]，即机器人全部处理完毕时到达最后一个工厂所需要的最小总距离。
算法 2 时间复杂度：O(n(m ^ 2))，其中 n 是机器人个数，m 是工厂个数。
空间复杂度：O(nm)。
算法 3：
1.首先对机器人位置数组 robot 进行排序，按照从小到大的顺序排列。
2.对工厂位置数组 factory 按照第一个元素排序，也就是按照工厂所在的位置从小到大排列。
3.创建一个二维数组 dp，大小为 (n, m)，其中 n 是机器人个数，m 是工厂个数。初始时，所有元素置为最大整数值。
4.创建一个双端队列 deque，用于维护每个工厂能够维修的机器人的最小距离。
5.遍历工厂，对于每个工厂，使用动态规划计算最小总距离。
--1.定义变量 add 表示当前机器人到当前工厂之前的距离和，初始化为 0。
--2.定义变量 limit 表示当前工厂能够维修的机器人数量限制。
--3.初始化双端队列 deque，将 (i, 0) 加入队列。其中 i 表示机器人的下标，0 表示到达当前工厂之前的距离和为 0。
--4.遍历机器人，计算当前状态下的最小距离。
----1.如果左边有一个工厂，选择它作为当前状态的备选值。
----2.从队列中取出所有与当前机器人距离小于等于 limit 的机器人，并计算这些机器人到当前工厂的距离和。如果队列为空，则跳过该步骤。
----3.在所有可能的状态中选择一个距离最小的状态，并将这个距离赋值给当前状态。
----4.将当前机器人加入队列，更新队列中的元素。
--5.返回 dp[n-1][m-1]，即机器人全部处理完毕时到达最后一个工厂所需要的最小总距离。
6.返回 dp[n-1][m-1]，即机器人全部处理完毕时到达最后一个工厂所需要的最小总距离。
时间复杂度：O(nm log n)，其中 n 是机器人个数，m 是工厂个数。
空间复杂度：O(nm)。
go 三种算法完整代码如下：
package main
import ( "fmt" "math" "sort")
func minimumTotalDistance1(robot []int, factory [][]int) int64 { n := len(robot) m := len(factory) sort.Ints(robot) sortFactoryByFirst(factory) dp := make([][]int64, n) for i := range dp { dp[i] = make([]int64, m) for j := range dp[i] { dp[i][j] = -1 } } return process1(robot, factory, n-1, m-1, dp)}
func process1(robot []int, factory [][]int, i, j int, dp [][]int64) int64 { if i < 0 { return 0 } if j < 0 { return math.MaxInt64 } if dp[i][j] != -1 { return dp[i][j] } ans := process1(robot, factory, i, j-1, dp) distance := int64(0) for l, num := i, 1; l >= 0 && num <= factory[j][1]; l, num = l-1, num+1 { curAns := process1(robot, factory, l-1, j-1, dp) d := int64(abs(robot[l] - factory[j][0])) distance += d if curAns != math.MaxInt64 { ans = min(ans, curAns+distance) } } dp[i][j] = ans return ans}
func sortFactoryByFirst(a [][]int) { sort.Slice(a, func(i, j int) bool { return a[i][0] < a[j][0] })}
func abs(x int) int { if x < 0 { return -x } return x}
func min(a, b int64) int64 { if a < b { return a } return b}
func minimumTotalDistance2(robot []int, factory [][]int) int64 { n := len(robot) m := len(factory) sort.Ints(robot) sortFactoryByFirst(factory) dp := make([][]int64, n) for i := 0; i < n; i++ { dp[i] = make([]int64, m) for j := 0; j < m; j++ { ans := int64(math.MaxInt64) if j > 0 { ans = dp[i][j-1] } distance := int64(0) for l, num := i, 1; l >= 0 && num <= factory[j][1]; l, num = l-1, num+1 { curAns := int64(0) if l-1 < 0 { curAns = 0 } else if j-1 < 0 { curAns = math.MaxInt64 } else { curAns = dp[l-1][j-1] } distance += int64(abs(robot[l] - factory[j][0])) if curAns != math.MaxInt64 { ans = min(ans, curAns+distance) } } dp[i][j] = ans } } return dp[n-1][m-1]}
func minimumTotalDistance3(robot []int, factory [][]int) int64 { n := len(robot) m := len(factory) sort.Ints(robot) sortFactoryByFirst(factory) dp := make([][]int64, n) for i := 0; i < n; i++ { dp[i] = make([]int64, m) for j := 0; j < m; j++ { dp[i][j] = math.MaxInt64 } } deque := make([][]int64, n+1) for i := 0; i < n+1; i++ { deque[i] = make([]int64, 2) } var l, r int for j := 0; j < m; j++ { add := int64(0) limit := int64(factory[j][1]) l = 0 r = 1 deque[l][0] = -1 deque[l][1] = 0 for i := 0; i < n; i++ { p1 := int64(math.MaxInt64) if j > 0 { p1 = dp[i][j-1] } add += int64(abs(robot[i] - factory[j][0])) if deque[l][0] == int64(i)-limit-1 { l++ } p2 := int64(math.MaxInt64) if l < r { best := deque[l][1] if best != math.MaxInt64 { p2 = add + best } } dp[i][j] = min(p1, p2) fill := p1 if p1 == math.MaxInt64 { fill = p1 } else { fill = p1 - add } for l < r && deque[r-1][1] >= fill { r-- } deque[r][0] = int64(i) deque[r][1] = fill r++ } } return dp[n-1][m-1]}
func main() { if true { robot := []int{0, 4, 6} factory := [][]int{{2, 2}, {6, 2}} fmt.Println(minimumTotalDistance1(robot, factory)) } if true { robot := []int{0, 4, 6} factory := [][]int{{2, 2}, {6, 2}} fmt.Println(minimumTotalDistance2(robot, factory)) }
if true { robot := []int{0, 4, 6} factory := [][]int{{2, 2}, {6, 2}} fmt.Println(minimumTotalDistance3(robot, factory)) }}
复制代码
rust 第 2 种和第 3 种算法代码如下：
fn minimum_total_distance2(robot: Vec<i32>, factory: Vec<Vec<i32>>) -> i64 { let n = robot.len(); let m = factory.len();
// 排序操作 let mut sorted_robot = robot.clone(); sorted_robot.sort_unstable();
let mut sorted_factory = factory.clone(); sorted_factory.sort_unstable_by_key(|a| a[0]);
let mut dp = vec![vec![std::i64::MAX; m]; n];
for i in 0..n { for j in 0..m { // ans = dp[i][j - 1] -> 0...i -> 0...j-1 let mut ans = std::i64::MAX; if j >= 1 { ans = dp[i][j - 1]; } let mut distance = 0; for (l, num) in (0..=i).rev().zip(1..=factory[j][1]) { let cur_ans = if l == 0 { 0 } else if j == 0 { std::i64::MAX } else { dp[l - 1][j - 1] }; let d = (robot[l] - factory[j][0]).abs() as i64; distance += d; if cur_ans != std::i64::MAX { ans = ans.min(cur_ans + distance); } } dp[i][j] = ans; } }
dp[n - 1][m - 1]}
fn minimum_total_distance3(robot: Vec<i32>, factory: Vec<Vec<i32>>) -> i64 { let n = robot.len(); let m = factory.len();
// 排序操作 let mut sorted_robot = robot.clone(); sorted_robot.sort_unstable();
let mut sorted_factory = factory.clone(); sorted_factory.sort_unstable_by_key(|a| a[0]);
let mut dp = vec![vec![std::i64::MAX; m]; n];
for j in 0..m { let mut add = 0; let limit = factory[j][1] as usize; let mut l = 0; let mut r = 1; let mut deque = vec![vec![0; 2]; n + 1]; deque[l][0] = std::i64::MAX; deque[l][1] = 0; for i in 0..n { let p1 = if j >= 1 { dp[i][j - 1] } else { std::i64::MAX }; add += (sorted_robot[i] - sorted_factory[j][0]).abs() as i64; while l < r && deque[l][0] == i as i64 - limit as i64 - 1 { l += 1; } let p2 = if l < r && deque[l][1] != std::i64::MAX { add + deque[l][1] } else { std::i64::MAX }; dp[i][j] = p1.min(p2); let fill = if p1 == std::i64::MAX { p1 } else { p1 - add }; while l < r && deque[r - 1][1] >= fill { r -= 1; } deque[r][0] = i as i64; deque[r][1] = fill; r += 1; } }
dp[n - 1][m - 1]}
fn main() { let robot = vec![0, 4, 6]; let factory = vec![vec![2, 2], vec![6, 2]]; println!( "{}", minimum_total_distance2(robot.clone(), factory.clone()) ); println!( "{}", minimum_total_distance3(robot.clone(), factory.clone()) );}
复制代码
c++三种算法完整代码如下：
#include <iostream>#include <vector>#include <algorithm>#include <climits>
using namespace std;
struct Pair { int x, y;};
void sortFactoryByFirst(vector<vector<int>>& factory) { sort(factory.begin(), factory.end(), [](const auto& a, const auto& b) { return a[0] < b[0]; });}
int64_t minimumTotalDistance1(vector<int>& robot, vector<vector<int>>& factory, int n, int m, vector<vector<int64_t>>& dp) { if (n < 0) { return 0; } if (m < 0) { return INT64_MAX; } if (dp[n][m] != -1) { return dp[n][m]; } int64_t ans = minimumTotalDistance1(robot, factory, n, m - 1, dp); int64_t distance = 0; for (int l = n, num = 1; l >= 0 && num <= factory[m][1]; l--, num++) { int64_t curAns = minimumTotalDistance1(robot, factory, l - 1, m - 1, dp); int64_t d = abs(robot[l] - factory[m][0]); distance += d; if (curAns != INT64_MAX) { ans = min(ans, curAns + distance); } } dp[n][m] = ans; return ans;}
int64_t minimumTotalDistance2(vector<int>& robot, vector<vector<int>>& factory, int n, int m) { sort(robot.begin(), robot.end()); sortFactoryByFirst(factory); vector<vector<int64_t>> dp(n, vector<int64_t>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int64_t ans = INT64_MAX; if (j > 0) { ans = dp[i][j - 1]; } int64_t distance = 0; for (int l = i, num = 1; l >= 0 && num <= factory[j][1]; l--, num++) { int64_t curAns = 0; if (l - 1 < 0) { curAns = 0; } else if (j - 1 < 0) { curAns = INT64_MAX; } else { curAns = dp[l - 1][j - 1]; } distance += abs(robot[l] - factory[j][0]); if (curAns != INT64_MAX) { ans = min(ans, curAns + distance); } } dp[i][j] = ans; } } return dp[n - 1][m - 1];}
int64_t minimumTotalDistance3(vector<int>& robot, vector<vector<int>>& factory, int n, int m) { sort(robot.begin(), robot.end()); sortFactoryByFirst(factory); vector<vector<int64_t>> dp(n, vector<int64_t>(m, INT64_MAX)); vector<Pair> deque(n + 1); int l = 0, r = 1; deque[0].x = -1; deque[0].y = 0; for (int j = 0; j < m; j++) { int64_t add = 0; int64_t limit = (int64_t)factory[j][1]; l = 0; r = 1; deque[l].x = -1; deque[l].y = 0; for (int i = 0; i < n; i++) { int64_t p1 = INT64_MAX; if (j > 0) { p1 = dp[i][j - 1]; } add += abs(robot[i] - factory[j][0]); while (l < r && deque[l].x == (int64_t)i - limit - 1) { l++; } int64_t p2 = INT64_MAX; if (l < r) { int64_t best = deque[l].y; if (best != INT64_MAX) { p2 = add + best; } } dp[i][j] = min(p1, p2); int64_t fill = p1; if (p1 == INT64_MAX) { fill = p1; } else { fill = p1 - add; } while (l < r && deque[r - 1].y >= fill) { r--; } deque[r].x = i; deque[r].y = fill; r++; } } return dp[n - 1][m - 1];}
int main() { if (true) { vector<int> robot{ 0, 4, 6 }; vector<vector<int>> factory{ {2, 2}, {6, 2} }; int n = robot.size(); int m = factory.size(); vector<vector<int64_t>> dp(n, vector<int64_t>(m, -1)); printf("%lld\n", minimumTotalDistance1(robot, factory, n - 1, m - 1, dp)); } if (true) { vector<int> robot{ 0, 4, 6 }; vector<vector<int>> factory{ {2, 2}, {6, 2} }; int n = robot.size(); int m = factory.size(); printf("%lld\n", minimumTotalDistance2(robot, factory, n, m)); } if (true) { vector<int> robot{ 0, 4, 6 }; vector<vector<int>> factory{ {2, 2}, {6, 2} }; int n = robot.size(); int m = factory.size(); printf("%lld\n", minimumTotalDistance3(robot, factory, n, m)); } return 0;}
复制代码
c 语言的不好写，故没有代码。
![2023-05-06：X轴上有一些机器人和工厂。给你一个整数数组robot，其中robot[i]是第i个机器人的位置 再给你一个二维整数数组factory，其中 factory[j] = [posit_golang_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论