最小移动总距离

2463. 最小移动总距离

X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 factory[j] = [position_j, limit_j] ，表示第 j 个工厂的位置在 position_j ，且第 j 个工厂最多可以修理 limit_j 个机器人。

每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置 。

所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 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 <= 100
factory[j].length == 2
-10⁹ <= robot[i], position_j <= 10⁹
0 <= limit_j <= robot.length
测试数据保证所有机器人都可以被维修。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) { } };

java 解法, 执行用时: 16 ms, 内存消耗: 39.7 MB, 提交时间: 2023-08-28 10:33:59

class Solution {
    public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
        Arrays.sort(factory, (a, b) -> a[0] - b[0]);
        var r = robot.stream().mapToInt(i -> i).toArray();
        Arrays.sort(r);
        var m = r.length;
        var f = new long[m + 1];
        Arrays.fill(f, (long) 1e18);
        f[0] = 0;
        for (var fa : factory)
            for (var j = m; j > 0; j--) {
                var cost = 0L;
                for (var k = 1; k <= Math.min(j, fa[1]); ++k) {
                    cost += Math.abs(r[j - k] - fa[0]);
                    f[j] = Math.min(f[j], f[j - k] + cost);
                }
            }
        return f[m];
    }
}

cpp 解法, 执行用时: 36 ms, 内存消耗: 8.1 MB, 提交时间: 2023-08-28 10:33:46

class Solution {
public:
    long long minimumTotalDistance(vector<int> &robot, vector<vector<int>> &factory) {
        sort(factory.begin(), factory.end(), [](auto &a, auto &b) { return a[0] < b[0]; });
        sort(robot.begin(), robot.end());
        int m = robot.size();
        long f[m + 1]; memset(f, 0x3f, sizeof(f));
        f[0] = 0;
        for (auto &fa: factory)
            for (int j = m; j > 0; j--) {
                long cost = 0L;
                for (int k = 1; k <= min(j, fa[1]); ++k) {
                    cost += abs(robot[j - k] - fa[0]);
                    f[j] = min(f[j], f[j - k] + cost);
                }
            }
        return f[m];
    }
};

golang 解法, 执行用时: 12 ms, 内存消耗: 2.3 MB, 提交时间: 2023-08-28 10:33:25

func minimumTotalDistance(robot []int, factory [][]int) int64 {
	sort.Slice(factory, func(i, j int) bool { return factory[i][0] < factory[j][0] })
	sort.Ints(robot)
	m := len(robot)
	f := make([]int, m+1)
	for i := range f {
		f[i] = 1e18
	}
	f[0] = 0
	for _, fa := range factory {
		for j := m; j > 0; j-- {
			for k, cost := 1, 0; k <= min(j, fa[1]); k++ {
				cost += abs(robot[j-k] - fa[0])
				f[j] = min(f[j], f[j-k]+cost)
			}
		}
	}
	return int64(f[m])
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

golang 解法, 执行用时: 24 ms, 内存消耗: 3.5 MB, 提交时间: 2023-08-28 10:33:11

func minimumTotalDistance(robot []int, factory [][]int) int64 {
	sort.Slice(factory, func(i, j int) bool { return factory[i][0] < factory[j][0] })
	sort.Ints(robot)
	n, m := len(factory), len(robot)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, m)
		for j := range dp[i] {
			dp[i][j] = -1
		}
	}
	var f func(int, int) int
	f = func(i, j int) (res int) {
		if j >= m {
			return
		}
		dv := &dp[i][j]
		if *dv != -1 {
			return *dv
		}
		defer func() { *dv = res }()
		if i == n-1 {
			if m-j > factory[i][1] {
				return 1e18
			}
			for _, x := range robot[j:] {
				res += abs(x - factory[i][0])
			}
			return
		}
		res = f(i+1, j)
		for s, k := 0, 1; k <= factory[i][1] && j+k-1 < m; k++ {
			s += abs(robot[j+k-1] - factory[i][0])
			res = min(res, s+f(i+1, j+k))
		}
		return
	}
	return int64(f(0, 0))
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

python3 解法, 执行用时: 1040 ms, 内存消耗: 16 MB, 提交时间: 2023-08-28 10:32:52

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        factory.sort(key=lambda f: f[0])
        robot.sort()
        m = len(robot)
        f = [0] + [inf] * m
        for pos, limit in factory:
            for j in range(m, 0, -1):
                cost = 0
                for k in range(1, min(j, limit) + 1):
                    cost += abs(robot[j - k] - pos)
                    f[j] = min(f[j], f[j - k] + cost)
        return f[m]

python3 解法, 执行用时: 1492 ms, 内存消耗: 23.5 MB, 提交时间: 2023-08-28 10:32:39

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        factory.sort(key=lambda f: f[0])
        robot.sort()
        n, m = len(factory), len(robot)
        @cache
        def f(i: int, j: int) -> int:
            if j == m: return 0
            if i == n - 1:
                if m - j > factory[i][1]: return inf
                return sum(abs(x - factory[i][0]) for x in robot[j:])
            res = f(i + 1, j)
            s, k = 0, 1
            while k <= factory[i][1] and j + k - 1 < m:
                s += abs(robot[j + k - 1] - factory[i][0])
                res = min(res, s + f(i + 1, j + k))
                k += 1
            return res
        return f(0, 0)

上一题

下一题

详情