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;
}
