千问 LeetCode 2463.最小移动总距离 C语言实现

这道题是 LeetCode 2463 最小移动总距离是一道经典的动态规划题。虽然题目本身没有提供C语言的标准解法但我们可以根据题解思路写出C语言实现。解题思路核心结论将机器人和工厂按位置排序后每个工厂修理的机器人一定是连续的一段。基于这个性质可以用动态规划求解- dp[i][j] 表示前 i 个工厂修理前 j 个机器人的最小总距离- 状态转移第 i 个工厂修理 k 个机器人0 ≤ k ≤ min(limit[i], j)则 dp[i][j] min(dp[i-1][j-k] cost)其中 cost 是这 k 个机器人到工厂的距离之和C语言实现#include stdlib.h#include string.h#include limits.h// 比较函数用于排序int cmp(const void* a, const void* b) {return *(int*)a - *(int*)b;}// 比较工厂位置int cmpFactory(const void* a, const void* b) {int* fa *(int**)a;int* fb *(int**)b;return fa[0] - fb[0];}long long minimumTotalDistance(int* robot, int robotSize, int** factory, int factorySize, int* factoryColSize) {// 1. 排序qsort(robot, robotSize, sizeof(int), cmp);qsort(factory, factorySize, sizeof(int*), cmpFactory);int m factorySize, n robotSize;// 2. 初始化dp数组dp[i][j] 表示前i个工厂修理前j个机器人的最小距离// 使用long long避免溢出long long dp[m 1][n 1];for (int i 0; i m; i) {for (int j 0; j n; j) {dp[i][j] LLONG_MAX / 2; // 初始化为大数}}dp[0][0] 0;// 3. 动态规划for (int i 1; i m; i) {dp[i][0] 0; // 不修任何机器人距离为0int pos factory[i-1][0]; // 工厂位置int limit factory[i-1][1]; // 工厂容量for (int j 1; j n; j) {// 先继承前i-1个工厂的状态第i个工厂不修机器人dp[i][j] dp[i-1][j];// 枚举第i个工厂修理k个机器人long long cost 0;int maxK limit j ? limit : j;for (int k 1; k maxK; k) {// 修理的机器人是连续的一段robot[j-k] 到 robot[j-1]cost abs(robot[j - k] - pos);// 更新状态if (dp[i-1][j-k] cost dp[i][j]) {dp[i][j] dp[i-1][j-k] cost;}}}}return dp[m][n];}复杂度分析- 时间复杂度O(m × n²)其中 m 是工厂数n 是机器人数- 空间复杂度O(m × n)示例验证以题目示例 robot [0,4,6], factory [[2,2],[6,2]] 为例- 排序后robot [0,4,6], factory [[2,2],[6,2]]- 最终结果4与题目一致优化建议如果追求更好的性能可以用前缀和优化距离计算将时间复杂度降到 O(m × n × limit)但实现会复杂一些。上面的实现已经足够应对题目中 n ≤ 100 的数据规模。