跳转至

1066. 校园自行车分配 II 🔒

题目描述

在由 2D 网格表示的校园里有 n 位工人（worker）和 m 辆自行车（bike），n <= m。所有工人和自行车的位置都用网格上的 2D 坐标表示。

我们为每一位工人分配一辆专属自行车，使每个工人与其分配到的自行车之间的 曼哈顿距离 最小化。

返回 每个工人与分配到的自行车之间的曼哈顿距离的最小可能总和 。

p1 和 p2 之间的 曼哈顿距离 为 Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|。

 

示例 1：

输入：workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
输出：6
解释：
自行车 0 分配给工人 0，自行车 1 分配给工人 1 。分配得到的曼哈顿距离都是 3, 所以输出为 6 。

示例 2：

输入：workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
输出：4
解释：
先将自行车 0 分配给工人 0，再将自行车 1 分配给工人 1（或工人 2），自行车 2 给工人 2（或工人 1）。如此分配使得曼哈顿距离的总和为 4。

示例 3:

输入：workers = [[0,0],[1,0],[2,0],[3,0],[4,0]], bikes = [[0,999],[1,999],[2,999],[3,999],[4,999]]
输出：4995

 

提示：

  • n == workers.length
  • m == bikes.length
  • 1 <= n <= m <= 10
  • workers[i].length == 2
  • bikes[i].length == 2
  • 0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
  • 所有的工人和自行车的位置都是 不同 的。

解法

方法一：状态压缩动态规划

我们定义 \(f[i][j]\) 表示前 \(i\) 个工人分配到自行车的状态为 \(j\) 时的最小曼哈顿距离总和，其中 \(j\) 是一个二进制数，表示自行车的分配情况。初始时 \(f[0][0]=0\)，其余 \(f[0][j]=+\infty\)。

考虑 \(f[i][j]\)，我们枚举第 \(i\) 个工人分配到的自行车的编号 \(k\)，那么 \(f[i][j]\) 可以从 \(f[i-1][j\oplus 2^k]\) 转移而来，其中 \(\oplus\) 表示异或运算。这是因为 \(f[i-1][j\oplus 2^k]\) 表示前 \(i-1\) 个工人分配到自行车的状态为 \(j\oplus 2^k\) 时的最小曼哈顿距离总和，而第 \(i\) 个工人分配到自行车 \(k\) 时，其曼哈顿距离为 \(|worker[i]-bike[k]|\)，其中 \(|x|\) 表示 \(x\) 的绝对值。因此我们可以列出状态转移方程：

\[ f[i][j]=\min_{k=0}^{m-1}\{f[i-1][j\oplus 2^k]+|worker[i]-bike[k]|\} \]

最终的答案为 \(\min_{j=0}^{2^m-1}\{f[n][j]\}\)。

时间复杂度 \(O(n \times 2^m \times m)\)，空间复杂度 \(O(n \times 2^m)\)。其中 \(n\) 和 \(m\) 分别是工人和自行车的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
        n, m = len(workers), len(bikes)
        f = [[inf] * (1 << m) for _ in range(n + 1)]
        f[0][0] = 0
        for i, (x1, y1) in enumerate(workers, 1):
            for j in range(1 << m):
                for k, (x2, y2) in enumerate(bikes):
                    if j >> k & 1:
                        f[i][j] = min(
                            f[i][j],
                            f[i - 1][j ^ (1 << k)] + abs(x1 - x2) + abs(y1 - y2),
                        )
        return min(f[n])

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int assignBikes(int[][] workers, int[][] bikes) {
        int n = workers.length;
        int m = bikes.length;
        int[][] f = new int[n + 1][1 << m];
        for (var g : f) {
            Arrays.fill(g, 1 << 30);
        }
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 1 << m; ++j) {
                for (int k = 0; k < m; ++k) {
                    if ((j >> k & 1) == 1) {
                        int d = Math.abs(workers[i - 1][0] - bikes[k][0])
                            + Math.abs(workers[i - 1][1] - bikes[k][1]);
                        f[i][j] = Math.min(f[i][j], f[i - 1][j ^ (1 << k)] + d);
                    }
                }
            }
        }
        return Arrays.stream(f[n]).min().getAsInt();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int n = workers.size(), m = bikes.size();
        int f[n + 1][1 << m];
        memset(f, 0x3f, sizeof(f));
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 1 << m; ++j) {
                for (int k = 0; k < m; ++k) {
                    if (j >> k & 1) {
                        int d = abs(workers[i - 1][0] - bikes[k][0]) + abs(workers[i - 1][1] - bikes[k][1]);
                        f[i][j] = min(f[i][j], f[i - 1][j ^ (1 << k)] + d);
                    }
                }
            }
        }
        return *min_element(f[n], f[n] + (1 << m));
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func assignBikes(workers [][]int, bikes [][]int) int {
    n, m := len(workers), len(bikes)
    f := make([][]int, n+1)
    const inf = 1 << 30
    for i := range f {
        f[i] = make([]int, 1<<m)
        for j := range f[i] {
            f[i][j] = inf
        }
    }
    f[0][0] = 0
    for i := 1; i <= n; i++ {
        for j := 0; j < 1<<m; j++ {
            for k := 0; k < m; k++ {
                if j>>k&1 == 1 {
                    d := abs(workers[i-1][0]-bikes[k][0]) + abs(workers[i-1][1]-bikes[k][1])
                    f[i][j] = min(f[i][j], f[i-1][j^(1<<k)]+d)
                }
            }
        }
    }
    return slices.Min(f[n])
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function assignBikes(workers: number[][], bikes: number[][]): number {
    const n = workers.length;
    const m = bikes.length;
    const inf = 1 << 30;
    const f: number[][] = new Array(n + 1).fill(0).map(() => new Array(1 << m).fill(inf));
    f[0][0] = 0;
    for (let i = 1; i <= n; ++i) {
        for (let j = 0; j < 1 << m; ++j) {
            for (let k = 0; k < m; ++k) {
                if (((j >> k) & 1) === 1) {
                    const d =
                        Math.abs(workers[i - 1][0] - bikes[k][0]) +
                        Math.abs(workers[i - 1][1] - bikes[k][1]);
                    f[i][j] = Math.min(f[i][j], f[i - 1][j ^ (1 << k)] + d);
                }
            }
        }
    }
    return Math.min(...f[n]);
}

评论