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语言的不好写，故没有代码。