这道题是 LeetCode 2463. 最小移动总距离题意为· 有 robot 的位置列表一维坐标。· 有 factory每个工厂有 position 和 limit能修的机器人数量。· 机器人移动距离 绝对位置差。· 每个工厂最多修 limit 个机器人。· 求所有机器人被修理的最小总移动距离。---思路分析这是一个 带容量限制的分配问题可以抽象为· 机器人位置 robot[i]排序后· 工厂位置 factories[j].position排序后每个工厂有容量 factories[j].limit。· 将机器人按某种顺序分配给工厂一个工厂修连续一段机器人因为交叉分配不会更优。最优性质将机器人和工厂都按坐标排序后最优解一定是 机器人按顺序分配给按顺序的工厂且每个工厂分配连续的一段机器人证明类似二分图匹配中的“无交叉”性质。---动态规划定义设· n len(robot)· m len(factory)将 robot 升序排序。将 factory 按位置升序排序。定义dp[i][j] 前 i 个工厂修理前 j 个机器人的最小总距离初始dp[0][0] 0dp[0][j0] INF无工厂时无法修机器人。---状态转移对于第 i 个工厂1-indexed我们考虑它修理第 k 到第 j 个机器人k 从 max(0, j - limit[i]) 到 jdp[i][j] min over k ( dp[i-1][k] cost(i, k1, j) )其中 cost(i, l, r) 表示第 i 个工厂修理机器人 l..r 的总距离。工厂位置 pos factory[i-1][0]机器人位置 robot[l-1..r-1]因代码中 0-index。由于修理连续的一段总距离cost sum_{tl}^r |robot[t-1] - pos|可以用 前缀和 快速计算。---优化直接计算 cost 是 O(n) 的总复杂度 O(m * n²) 会很大n100, m100 勉强可过其实会超时。需要优化设· prefix[t] sum_{u0}^{t-1} robot[u]· 求 sum_{tl}^r |robot[t] - pos|。对于有序 robot可以在 [l, r] 中找分界点 mid使得 robot[mid] pos robot[mid1]则cost pos*(mid-l1) - sum(l..mid) sum(mid1..r) - pos*(r-mid)用二分找到 mid前缀和 O(1) 算。这样转移 O(n log n) 总体 O(m * n² log n) 仍大但 n ≤ 100 时可行。更优做法直接枚举 k 时cost 可以用递推 O(1) 维护不过实现略复杂。---实现简洁版javaimport java.util.*;class Solution {public long minimumTotalDistance(ListInteger robot, int[][] factory) {// 排序Collections.sort(robot);Arrays.sort(factory, (a, b) - a[0] - b[0]);int n robot.size();int m factory.length;// dp[i][j] 前 i 个工厂修前 j 个机器人的最小距离long[][] dp new long[m 1][n 1];for (int i 0; i m; i) Arrays.fill(dp[i], Long.MAX_VALUE / 2);dp[0][0] 0;// 机器人位置前缀和方便算 costlong[] prefix new long[n 1];for (int i 0; i n; i) prefix[i 1] prefix[i] robot.get(i);for (int i 1; i m; i) {int pos factory[i - 1][0];int limit factory[i - 1][1];// 先用上一个工厂的状态for (int j 0; j n; j) dp[i][j] dp[i - 1][j];// 当前工厂修 k 个机器人for (int j 1; j n; j) {// 当前工厂最多修 limit 个所以它修的数量 t j - kfor (int t 1; t Math.min(limit, j); t) {int k j - t; // 前面 k 个机器人已由前 i-1 个工厂修完if (dp[i - 1][k] Long.MAX_VALUE / 2) continue;// 当前工厂修机器人 [k .. j-1] (0-index)// 机器人索引k..j-1long cost 0;int l k, r j - 1; // 在 robot 中的索引范围// 二分找分界点int lo l, hi r;while (lo hi) {int mid (lo hi) / 2;if (robot.get(mid) pos) lo mid 1;else hi mid - 1;}int split hi; // 最后一个 pos 的索引long sumLeft (split l) ? (prefix[split 1] - prefix[l]) : 0;long sumRight (split 1 r) ? (prefix[r 1] - prefix[split 1]) : 0;int leftCount (split l) ? (split - l 1) : 0;int rightCount (r - split);cost pos * (long) leftCount - sumLeft;cost sumRight - pos * (long) rightCount;dp[i][j] Math.min(dp[i][j], dp[i - 1][k] cost);}}}return dp[m][n];}}---复杂度· 排序O(n log n m log m)· DPO(m * n * limit)最坏 O(m * n²)因为 limit 可能 ≈ n· 在题目限制 n ≤ 100, m ≤ 100 下可接受。