登录利用关键结论进行 DP，含证明
解法：DP
设机器人有 $n$ 个，工厂有 $m$ 个。不失一般性地，假设机器人的坐标是递增的，工厂的坐标也是递增的。
关键结论
设最优方案中，机器人 $i$ 被送去工厂 $t_i$。注意到关键结论
存在最优方案，使得 $t_i$ 是不严格单调递增的。
证明
引理：若存在 $1 \le x < y \le n$ 满足 $t_x > t_y$，此时让机器人 $x$ 去工厂 $t_y$，机器人 $y$ 去工厂 $t_x$，答案不会变得更差。
不失一般性地，设机器人 $x$ 的坐标小等于工厂 $t_x$ 的坐标（若实际情况不是如此，将机器人 $x$ 和工厂 $t_x$ 的坐标对换，机器人 $y$ 和工厂 $t_y$ 的坐标对换，可以发现距离不变）。为了证明引理，对以下三种情况进行讨论：
相信看过我的题解的朋友会觉得这张图很眼熟。没错，这张图和第 316 场周赛的 使数组相似的最少操作次数 几乎一模一样。
DP
有了关键结论，我们就能用 DP 求最优答案。既然 $t_i$ 是不严格单调递增的，我们就对每一段相同的 $t_i$ 进行 DP。
设 $d(l, r, x)$ 表示将第 $l$ 到 $r$ 个机器人都送去工厂 $x$ 的总距离。维护 $f(i, j)$ 表示已经送走了前 $i$ 个机器人，且第 $i$ 个机器人送去工厂 $j$ 的最小总距离。转移方程为
$$
f(i, j) = \min\limits_{0 \le i' < i, 0 \le j' < j} (f(i', j') + d(i' + 1, i, j)) \quad \text{s.t. } \quad i - i' \le \text{工厂 } j \text{ 的容量}
$$
这个转移方程就是在枚举把哪一段的机器人全部送去工厂 $j$。初值 $f(0, 0) = 0$。答案就是 $\min\limits_{j=1}^m f(n, j)$。
最小的 $f(i', j')$ 用前缀 min 维护即可。令 $g(i, j) = \min\limits_{0 \le j' \le j} f(i, j')$，那么转移方程可以改为
$$
f(i, j) = \min\limits_{0 \le i' < i} (g(i', j - 1) + d(i' + 1, i, j)) \quad \text{s.t. } \quad i - i' \le \text{工厂 } j \text{ 的容量}
$$
初值 $f(0, 0) = 0$，$g(0, *) = 0$。答案就是 $g(n, m)$。复杂度 $\mathcal{O}(n\log n + m\log m + n^2m)$。
参考代码（c++）
###c++
class Solution {
public:
long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
// 机器人和工厂的坐标排序
sort(robot.begin(), robot.end());
sort(factory.begin(), factory.end());
const long long INF = 1e15;
int n = robot.size(), m = factory.size();
// g[i][j] 表示 min(f[i][j'])，j' <= j
long long f[n + 1][m + 1], g[n + 1][m + 1];
// 初值
for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) f[i][j] = g[i][j] = INF;
f[0][0] = 0;
for (int j = 0; j <= m; j++) g[0][j] = 0;
// 套转移方程
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
long long d = 0;
for (int ii = i - 1; ii >= 0 && i - ii <= factory[j - 1][1]; ii--) {
d += abs(robot[ii] - factory[j - 1][0]);
f[i][j] = min(f[i][j], g[ii][j - 1] + d);
}
}
for (int j = 1; j <= m; j++) g[i][j] = min(g[i][j - 1], f[i][j]);
}
return g[n][m];
}
};
