2463. 最小移动总距离
考点
- 贪心
- 划分DP
- 滚动数组
- 前缀和
思路
首先可以发现，每次优先取工厂周围的机器人（因为所有机器人速度一样，离得近必定先填满工厂）这个贪心思路是错的
道理很简单，假设x工厂能存两个人，y工厂能存一个人，按照贪心，x直接处理B和C，那么A只能去y
显然这是不如A、B去x，C去y的
1 | A B x C y |
那么思考一下这个办法，每次都构造一个连续数组依次给工厂会怎样？
先把机器人和工厂按坐标排好序：
- 机器人位置：\(r_1 \le r_2 \le \dots \le r_n\)
- 工厂位置：\(f_1 \le f_2 \le \dots \le f_m\)
任何一个合法分配，可以写成一个长度为 n 的数组：
a[i] = 机器人 i 去的工厂编号（工厂编号从 1~m）
比如有 7 个机器人、3 个工厂，某个分配长这样：
1 | 机器人下标 i: 1 2 3 4 5 6 7 |
可以看出：
- 工厂 1 负责机器人 1~2
- 工厂 2 负责机器人 3~5
- 工厂 3 负责机器人 6~7
它们对应的都是一段连续下标。
我们要证明的是：一定存在一个最优解，它的 a[i] 是“单调不减”的， 也就是像上面的例子这样：
1 | 1 1 2 2 2 3 3 （非降序） |
而不是：
1 | 1 3 2 2 3 3 （先大后小，乱跳） |
一旦 a[i] 是单调不减的，你马上得到：
每个工厂的编号只会出现在一段连续的位置里（或者不出现）， 所以“每个工厂负责一段连续的机器人”。
证明该贪心的可行性，尝试用邻值交换法：
设有两个机器人 i, k（i < k），两个工厂 j, ℓ（j < ℓ）。
- 机器人坐标排好：\(r_i \le r_k\)
- 工厂坐标排好：\(f_j \le f_\ell\)
如果现在分配是「交叉」的：
- 机器人 i → 工厂 ℓ
- 机器人 k → 工厂 j
那这两条的总距离是： \[ D_\text{交叉} = |r_i - f_\ell| + |r_k - f_j| \] 如果我们把它 改成不交叉：
- 机器人 i → 工厂 j
- 机器人 k → 工厂 ℓ
总距离变成： \[ D_\text{直连} = |r_i - f_j| + |r_k - f_\ell| \] 在一条数轴上，点的顺序是：
1 | f_j ------ f_ℓ ------> （工厂从左到右） |
这显然就是一个四边形，左的配左、右的配右就是两条斜边，而左的配右、右的配左就是两条对角线，斜边怎么可能会比对角线还大呢？那么就得到贪心思路：
左的配左、右的配右，一定不比“左的配右、右的配左”更差： \[ D_\text{直连} \le D_\text{交叉} \]
难点解决之后就是简单的划分DP编程了
既然是一个「按顺序划分机器人序列」的 DP，最自然的状态是：
1 | dp[i][j]：用前 j 个工厂，修好前 i 个机器人的最小总距离。 |
即
1 | 机器人: r1 r2 r3 r4 r5 ... rn |
dp[i][j]表示我们已经决定好：
- 对工厂 1..j 的分配
- 它们共同处理了机器人 r1..ri（每个工厂一段，可能有工厂空着不用）
初始化如下：
dp[0][j] = 0： 前 0 个机器人都不用修，自然是 0 代价，无论用了多少工厂。dp[i][0]= +∞（i > 0）： 0 个工厂无法修任何机器人。
既然是划分 DP，转移的模板几乎都是：
「枚举最后一块（最后一段）的长度」。
在这里，“最后一块”就是：第 j 个工厂修的那批机器人，是前 i 个机器人的一个结尾段： \[ \text{第 j 工厂修 } r_{i-k+1}, \dots, r_i \] 用文字 + 小图看：
1 | r1 r2 r3 r4 r5 r6 r7 r8 |
设这一段的长度为 k：
- 段为 \(r_{i-k+1}, \dots, r_i\)
- k 不能超过工厂 j 的容量 cap[j]，也不能超过 i（因为最多用掉前 i 个机器人）：
\[ 1 \le k \le \min(i, cap[j]) \]
那当第 j 个工厂负责这一段时的总成本是：
- 前面 i-k 个机器人由前 j-1 个工厂修：
dp[i-k][j-1] - 再加上 工厂 j 修当前这 k 个机器人的距离和：
\[ \text{cost}(j, i-k+1, i) = \sum_{t=i-k+1}^{i} |r_t - f_j| \]
所以转移式子就是： \[
dp[i][j] = \min_{k = 0}^{\min(i, cap[j])} \Big( dp[i-k][j-1] +
\sum_{t=i-k+1}^{i} |r_t - f_j| \Big)
\] 注意这里允许 k = 0，表示“第 j 个工厂不修机器人”，
此时那一项退化为dp[i][j-1]，也就是“前 j-1 个工厂已经修完前
i 个机器人”，满足“某些工厂闲置不用”的情况。
因为工厂 j 的位置是固定的 f_j，我们可以对每个工厂 j 预处理一条「距离前缀和」： \[ prefix[j][i] = \sum_{t=1}^i |r_t - f_j| \] 画个小图（工厂 j 固定）：
1 | 机器人下标: 1 2 3 4 5 6 ... |
那段 \(r_l..r_r\)
的总距离就是一截区间和： \[
\text{cost}(j, l, r) = prefix[j][r] - prefix[j][l-1]
\] 在我们的状态转移里 l = i-k+1, r = i，因此： \[
\text{cost}(j, i-k+1, i) = prefix[j][i] - prefix[j][i-k]
\] 于是转移可以写成： \[
dp[i][j] = \min_{k = 0}^{\min(i, cap[j])} \Big( dp[i-k][j-1] +
prefix[j][i] - prefix[j][i-k] \Big)
\] 得到AC代码：
1 | class Solution { |
当然，也可以滚掉j那一维，记得把i放在外循环并倒序，j放在内循环即可
1 | class Solution { |