1. 项目概述从“移动”这道题看蓝桥杯算法训练的核心最近在带学生备赛蓝桥杯翻看历年真题时ALGO-979 “移动”这道题总是能引起不少讨论。题目名字听起来简单直白但恰恰是这种看似基础的题目最能考验选手对算法本质的理解和代码实现的扎实程度。它不像一些复杂的数据结构题那样有华丽的“外衣”而是直指算法竞赛中的一个核心思想如何将实际问题抽象为数学模型并用最优的路径去解决它。很多新手一看到“移动”可能下意识地就想用模拟法一步步去推演这在数据量小的时候没问题可一旦数据规模上来模拟法的时间复杂度可能直接导致程序超时。这道题就是一个很好的分水岭区分的是“会写代码”和“会用算法思维解决问题”的两种能力层级。它适合所有正在从语法学习过渡到算法训练的编程爱好者尤其是那些感觉刷了很多题却进步缓慢或者一遇到稍复杂的逻辑就无从下手的同学。通过深度拆解这道题我们不仅能搞定一个具体的题目更能掌握一种“化繁为简寻找规律”的解题通法。2. 题目核心逻辑与抽象建模2.1 问题场景还原与初步分析ALGO-979 “移动”的典型描述通常是在一个数轴上有若干个点可以想象成棋子或物体给定它们的初始位置。现在需要将它们通过移动最终变为连续相邻的若干个位置比如最终占据位置1, 2, 3, ...。每次移动可以将一个点向左或向右移动一个单位距离代价为1。题目要求找出使所有点变为连续序列所需的最小总移动代价。举个例子假设初始点为 [1, 2, 4, 7]。我们希望它们最终连续。一个直观但低效的想法是尝试所有可能的最终连续区间比如让它们最终占据[1,2,3,4]或者[2,3,4,5]然后计算每个点移动到目标位置的距离之和取最小值。这里就引出了第一个关键点最终连续序列的确定。假设有n个点最终连续序列的长度也一定是n。那么这个序列的起始位置或者说左端点L是多少如果我们枚举所有可能的L计算复杂度会很高。我们需要更聪明的方法。2.2 关键数学模型建立中位数的威力这里就涉及到算法竞赛中一个非常经典的贪心策略当代价是移动的绝对距离时将所有点移动到同一个目标位置最优的目标位置是所有点的中位数。这个结论可以通过数学证明绝对值函数 |x - target| 的和当target取中位数时最小。对于“移动”这道题情况类似但稍有扩展。我们的目标不是同一个点而是一个连续的区间。一个经典的转化思路是先将点排序。假设排序后的点为 a[0], a[1], ..., a[n-1]。我们希望它们最终变为连续区间 [L, L1, ..., Ln-1]。那么对于排序后的第 i 个点 a[i]它理想的目标位置就是 L i。因此总代价 cost(L) Σ |a[i] - (L i)|其中 i 从 0 到 n-1。 令 b[i] a[i] - i。那么上式变为 cost(L) Σ |b[i] - L|。惊喜出现了问题被完美转化为为数列 b 寻找一个最优的 L使得所有 b[i] 到 L 的绝对距离之和最小。而这正是我们熟悉的“中位数”问题。所以最优的 L 就是数列 b 的中位数。注意这个转化是本题的核心技巧也是很多选手卡住的地方。理解的关键在于将“移动到连续位置”这个条件通过引入索引 i巧妙地合并到了目标位置表达式中从而将二维问题降维为一维的中位数问题。2.3 算法步骤拆解基于以上分析我们可以将解题步骤固化下来输入与排序读取点的个数 n 和初始坐标数组 a。对数组 a 进行升序排序。这是所有后续操作的基础。构造新数组 b创建新数组 b其中 b[i] a[i] - i。这一步实现了问题的关键转化将“连续”的约束吸收了。寻找中位数对数组 b 进行排序或者用快速选择算法找到第 k 大的数。中位数的取法取决于 n 的奇偶性如果 n 是奇数中位数就是 b[n/2]下标从0开始。如果 n 是偶数理论上取 b[n/2 - 1] 和 b[n/2] 之间的任意值都可以得到最小和。通常为了计算方便我们可以取 b[n/2]或 b[n/2 - 1]因为最终代价需要整数而中位数本身是整数时取这两个之一结果一样。更稳妥的做法是计算这两个值作为 L 得到的代价取最小值。但在本题的离散整数场景下取 b[n/2] 作为 L 在绝大多数情况下是正确的。计算最小总代价确定最优的 L 后代入公式计算总代价min_cost Σ |a[i] - (L i)|。也可以等价地计算 Σ |b[i] - L|。输出结果。3. 代码实现与细节剖析3.1 基础版本代码实现C示例掌握了理论代码实现就相对直接了。这里给出一个清晰、易读的C实现版本并附上关键注释。#include iostream #include vector #include algorithm #include cmath // 用于abs函数 using namespace std; int main() { int n; cin n; vectorlong long a(n); // 使用long long防止大数溢出 for (int i 0; i n; i) { cin a[i]; } // 步骤1: 排序 sort(a.begin(), a.end()); // 步骤2: 构造数组b vectorlong long b(n); for (int i 0; i n; i) { b[i] a[i] - i; } // 步骤3: 找到数组b的中位数 // 为了找中位数需要将b排序。注意这里排序b不会影响原问题逻辑。 sort(b.begin(), b.end()); long long L b[n / 2]; // 取中位数作为最优的连续序列起始点L // 步骤4: 计算最小总代价 long long min_cost 0; for (int i 0; i n; i) { // 计算每个点移动到其目标位置 L i 的距离 min_cost abs(a[i] - (L i)); // 也可以使用min_cost abs(b[i] - L); 但注意此时的b[i]是排序前的吗 // 更清晰的做法是直接用a[i]和Li计算。 } cout min_cost endl; return 0; }3.2 关键细节与优化讨论数据类型选择坐标和代价可能很大int类型可能溢出务必使用long longC或longJava/Python自动处理大整数。这是竞赛中非常常见的失分点。中位数计算的优化上述代码对数组 b 进行了排序时间复杂度是 O(n log n)。实际上我们只需要找到第 k 大的数中位数可以使用快速选择算法QuickSelect其平均时间复杂度为 O(n)。这在 n 非常大时虽然本题一般不会是一个优化点。但考虑到代码简洁性和可读性直接排序在竞赛中通常是可接受的。偶数长度情况处理当 n 为偶数时中位数区间是 [b[n/2 - 1], b[n/2]]。取区间内任意整数作为 L 得到的代价是一样的吗在离散整数和绝对值距离下不一定。最严谨的做法是计算 L b[n/2 - 1] 和 L b[n/2] 分别对应的代价取较小值。但经过大量测试和理论分析对于本题的此类“移动”问题取b[n/2]作为 L 总能得到正确结果。为了代码健壮性你可以实现一个calc_cost(L)函数然后尝试L b[n/2-1]和L b[n/2]输出最小代价。空间优化我们完全可以不显式创建数组 b。在排序 a 之后可以在计算代价的循环中直接使用a[i] - i的概念。但创建 b 数组有助于理解代码逻辑更清晰。在内存充足的情况下清晰优于微小的优化。3.3 一个完整的、带稳健性处理的代码示例下面提供一个更稳健的版本处理了 n 为偶数的情况并封装了代价计算函数。#include iostream #include vector #include algorithm #include cmath #include climits // 用于LLONG_MAX using namespace std; // 计算当最终连续序列起始点为L时的总代价 long long calculate_cost(const vectorlong long a, long long L) { long long cost 0; for (size_t i 0; i a.size(); i) { cost abs(a[i] - (L i)); } return cost; } int main() { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); vectorlong long b(n); for (int i 0; i n; i) { b[i] a[i] - i; } // 找中位数候选 sort(b.begin(), b.end()); long long candidate_L1 b[n / 2]; long long min_cost calculate_cost(a, candidate_L1); // 如果n是偶数检查另一个中位数候选 if (n % 2 0) { long long candidate_L2 b[n / 2 - 1]; long long cost2 calculate_cost(a, candidate_L2); if (cost2 min_cost) { min_cost cost2; } } cout min_cost endl; return 0; }4. 算法原理深度探讨与变种思考4.1 为什么是中位数一个直观解释很多同学记住了“绝对值最小和找中位数”的结论但未必理解其本质。我们可以这样想假设有一条数轴上面有若干个点。你要找一个点L使得所有点到L的距离之和最小。如果你把L向右移动一小步那么它左边的所有点离L都远了一步右边的所有点离L都近了一步。所以当L左右两边的点数不相等时你总可以通过向点数多的一侧移动来减少总距离。只有当L左右两边的点数相等或尽可能接近时移动才会导致一边增加的距离等于另一边减少的距离总和达到最小。这个位置就是中位数。对于本题转化后的b[i] - L道理完全相同。中位数保证了“力”的平衡。4.2 变种与扩展思考“移动”问题有很多变种理解核心模型后可以举一反三移动代价为距离的平方如果移动一个点d单位距离的代价是d^2那么最优目标位置就不再是中位数而是算术平均数。这是因为最小化平方和函数Σ(x_i - t)^2求导后导数为零的点t (Σ x_i) / n。最终形态不是连续序列而是所有点重合这就是经典的中位数问题原型。代价为Σ |a[i] - L|最优 L 是a[i]的中位数。二维平面上的“移动”如果有多个点需要移动到同一位置代价是曼哈顿距离|x1-x2| |y1-y2|那么 x 坐标和 y 坐标是独立的最优目标点的 x 坐标是所有点 x 坐标的中位数y 坐标是所有点 y 坐标的中位数。问题被分解为两个一维中位数问题。带权重的移动每个点有一个权重 w_i移动它的代价是w_i * |a[i] - target|。这时最优 target 是加权中位数weighted median即满足“左边权重和”与“右边权重和”都小于等于总权重一半的位置。4.3 在蓝桥杯中的考查形式与应对策略ALGO-979这类题属于“思维题”或“数学结论题”。在蓝桥杯中它可能不会直接以“移动”这个名字出现但核心模型最小化绝对距离和会隐藏在其他场景下比如仓库选址问题在一条路上建仓库服务多个客户最小化运输距离。会议选址问题使所有人到会场的总距离最小。调整数组元素使其满足某种等差或连续关系。应对策略识别模型看到“最小化移动距离”、“最小化代价”、“调整位置”等关键词且代价与距离成正比就要联想到中位数或平均数模型。验证转化仔细分析最终目标状态看能否像本题一样通过引入索引等方式将复杂条件转化为简单的“点到单一目标”的距离问题。注意数据类型和边界这是实现层面的硬性要求必须养成习惯。5. 常见错误与调试技巧实录在辅导学生和自己刷题的过程中我总结了几类常见的“坑点”5.1 典型错误清单未排序直接计算这是最致命的错误。中位数策略的前提是点是有序的或者更具体地说在构造b[i] a[i] - i时这个i是排序后数组的索引。如果a没有排序b数组就失去了意义后续计算全是错的。整数溢出这是竞赛老生常谈的问题。输入坐标范围、n的大小题目一般会给出。如果坐标绝对值在10^9n在10^5那么总代价可能达到10^14远超32位int的范围约2*10^9。必须使用64位整数C的long long Java的long Python的int自动支持大数。中位数下标取错在C中数组下标从0开始。对于排序后的数组b中位数位置是b[n/2]n为奇数或b[n/2]和b[n/2-1]n为偶数。这里n/2是整数除法。例如 n5, n/22第三个元素是中位数n4, n/22, n/2-11第二和第三个元素是中位数区间。误解最终状态有同学会误以为最终连续序列必须从1开始或者必须包含0。题目通常只说“连续”起始位置 L 是需要我们求解的变量。我们的算法正是为了找到这个最优的 L。偶数n时处理不当如前所述最稳妥的方法是计算两个候选 L 的代价。只取一个有时也能AC但依赖于数据。养成严谨的习惯在竞赛中很重要。5.2 调试与测试用例设计当你写完代码如何快速验证其正确性设计小规模暴力验证用例对于 n 很小比如 n8的情况你可以写一个暴力程序枚举所有可能的最终连续序列的起始位置 L范围可以设得大一些比如从min(a[i]) - n到max(a[i]) n计算每种情况下的总代价找出最小值。用这个最小值来验证你的中位数算法结果是否正确。这是验证算法正确性的黄金标准。典型测试用例用例1n3, a[1, 2, 4]。排序后为[1,2,4]。b[1-0, 2-1, 4-2] [1,1,2]。b的中位数是1。L1。最终位置应为[1,2,3]。代价|1-1||2-2||4-3|1。也可以枚举最终为[1,2,3]代价1[2,3,4]代价|1-2||2-3||4-4|2[0,1,2]代价|1-0||2-1||4-2|4。最小为1。正确。用例2n4, a[1, 2, 4, 7]文章开头的例子。排序后[1,2,4,7]。b[1,1,2,4]。b排序后为[1,1,2,4]。n为偶数候选L1b[2]2候选L2b[1]1。L2目标位置[2,3,4,5]代价|1-2||2-3||4-4||7-5| 11024。L1目标位置[1,2,3,4]代价|1-1||2-2||4-3||7-4| 00134。 最小代价为4。可以暴力枚举验证。用例3n1, a[100]。只有一个点它本身就是一个连续序列代价为0。你的程序应该能处理 n1 的情况。b[100-0][100]L100代价|100-(1000)|0。用例4负数和大数。n2, a[-1000000000, 1000000000]。排序后[-1e9, 1e9]。b[-1e9-0, 1e9-1] [-1e9, 999999999]。b排序后[-1e9, 999999999]。n为偶数候选L1b[1]999999999候选L2b[0]-1e9。L999999999目标位置[999999999, 1000000000]代价|-1e9-999999999| |1e9-1e9| ≈ 1999999999 0。注意计算时可能溢出要用long long。L-1e9目标位置[-1e9, -999999999]代价| -1e9 - (-1e9) | |1e9 - (-999999999)| 0 1999999999。 最小代价为1999999999。这个用例可以测试溢出和负数处理。使用调试输出在代码关键步骤后打印中间变量如排序后的a、计算出的b、找到的L等。与手动计算或小规模暴力程序的结果对比可以快速定位逻辑错误。6. 从解题到举一反三算法思维的培养ALGO-979 “移动”的价值远不止于解出一道题。它提供了一个绝佳的范本展示了如何应对一类算法问题问题抽象剥离具体场景移动棋子、调整位置识别出核心操作移动和代价模型绝对距离。模型转化通过引入索引i将“移动到连续位置”的复杂约束转化为“移动到Li”的简单形式进而合并为“移动到固定点 L”的经典问题。这种“通过变量替换或重新定义问题来简化约束”的技巧非常强大。应用已知结论转化后的问题匹配了经典算法模型中位数求最小绝对距离和直接应用高效解法。注意边界与实现细节数据类型、排序、中位数索引、偶数情况等是最终将正确思路转化为AC代码的保障。在平时的训练中遇到类似题目要有意识地进行这种“四步走”分析。例如蓝桥杯另一道经典题“货仓选址”在一条数轴上选一个点建仓库使到各商店距离和最小就是本题“最终形态为重合”的简化版直接找中位数即可。再比如一些调整数组使差值最小的问题也可能蕴含类似思想。最后关于代码实现我个人习惯在竞赛中优先保证清晰正确在时间复杂度允许的情况下如本题O(n log n)对n10^5绰绰有余不过早追求极致的优化如用快速选择代替排序。先把稳拿分的代码写出来检查好边界条件比为了快几毫秒而引入复杂性和潜在bug要重要得多。这道题的核心收获应该是掌握“中位数”这个工具在解决一类最优化问题中的妙用以及学会如何通过数学变换将新问题规约到旧模型。这才是算法训练从“刷题”走向“通法”的关键一步。