蚂蚁的春招笔试从3月初就陆续铺开了3月12日这场在线笔试的第一题叫“增加or减少”满分100分。题目本身非常短核心就一句话给你一个整数数组每次操作可以把任意一个数加1或者减1问最少操作多少次能让所有数相等。说实话这道题在算法竞赛里属于入门级但在校招笔试里出现恰好能刷掉一批“背了八股文但基础不扎实”的人。很多人一看题第一反应是求平均值提交完才发现全是WA。这篇文章我把完整解析写下来读题、推思路、JavaCPython三种语言实现以及在线测试时我自己踩过的坑都拆开讲一遍。如果你正在准备2026年春招或者想在牛客、力扣这类平台上练手这篇可以直接照着写。1. 题目描述每次加一或减一目标是最小总操作次数1.1 输入输出与数据范围先还原一下题目场景。输入分两行第一行一个整数n表示数组长度第二行n个整数表示初始数组a[1..n]输出一个整数表示最少操作次数。样例是这样的输入 3 1 2 3 输出 2解释把1加一次变成2把3减一次变成2总共操作2次数组变成[2,2,2]。数据范围我没有拿到官方准确版本但按照蚂蚁春招第一题的惯例和100分的定位n一般给到10^5量级数组元素的绝对值可能到10^9。这个数据范围直接决定了两个关键点算法复杂度必须控制在O(n log n)以内暴力枚举目标值这种O(n * 值域)的方案不用考虑最终答案必须用64位整数存int一定会溢出这点后面细说。1.2 平均数是最容易踩的坑“增加or减少”这个名字很有迷惑性其实操作只有两种选一个数 1或者选一个数 -1。每次操作代价都是1最后所有数要相等。这个“相等后的目标值”到底是多少是整个题的核心。很多人一看到“让所有数相等”条件反射就去求平均值。比如数组[1, 2, 100]平均值约34.33取整到34的话代价是|1-34| |2-34| |100-34| 33 32 66 131。但如果你取中位数2代价是|1-2| |2-2| |100-2| 1 0 98 99直接省下32次操作。原因也很直观平均值会被极端值拉偏而最终相等的那个值不需要讨好所有数它需要的是让“整体移动距离”最小。极端值一个人走远路比拖着平均值让所有人都走远路要划算得多。所以结论在第一眼就该建立起来这道题的目标值不是平均数而是中位数。2. 解题思路为什么“中位数”是最优目标值2.1 把问题翻译成一个数学表达式假设最终所有数都变成x那么总操作次数可以写成f(x) |a1 - x| |a2 - x| ... |an - x|我们要找的就是让f(x)最小的那个x。f(x)是n个绝对值函数之和整体是一个凸函数画出来像一个碗碗底就是最小值点。在数轴上直观想象一下把所有a[i]画成数轴上的点f(x)就是这些点到x的“路程总和”。当x在数轴上从左往右移动的时候左边每个点离它越来越远右边每个点离它越来越近总路程的变化率就等于“右边点的个数减去左边点的个数”。要让总路程最小就得让左右两边点的数量尽量平衡。也就是说x应该落在数轴中间的位置——中位数。这个解释已经接近答案了但还可以更严格一点。2.2 用配对抵消的方式证明中位数最优这个证明不需要高数用初等放缩就能说清楚。先把数组排好序得到a1 a2 ... a(n-1) an然后从外往里配对(a1, an)、(a2, a(n-1))、…… 这样一直配到中间。对于任意一对(a[i], a[j])只要x落在区间[a[i], a[j]]内就有|x - a[i]| |x - a[j]| a[j] - a[i]也就是说这一对的距离和是一个定值跟x具体取区间内哪个点无关。如果x落在区间外面这一对的距离和会变大。所以要让所有配对的距离和都达到最小值就必须让x同时落在每一对的区间里。随着配对从外层往内层走区间不断收缩最后剩下中间的一个点n为奇数或者中间的一段区间n为偶数。这个点或这段区间就是中位数所在位置。这个证明非常干净我每次给别人讲对方都能秒懂。有了这个结论代码主流程就简单了1. 对数组排序 2. 目标值 target 排序后第 n/2 个元素 3. ans 0 4. 遍历数组ans |a[i] - target|有个小细节容易忽略n为偶数时中位数有两个到底取哪个答案是都行。因为中间两个数之间的任意值都不会改变每一对的距离和所以取arr[n/2]和arr[n/2 - 1]结果完全一样。为了避免边界判断统一取arr[n/2]就行。2.3 复杂度分析与代码主流程时间复杂度排序O(n log n)扫描一遍O(n)总体O(n log n)。空间复杂度如果不额外开数组排序是原地操作额外空间O(1)不考虑递归栈的话。n 10^5时O(n log n)在三种语言下都能轻松跑完这也是为什么题目给到 100 分——它考的不是复杂的算法模板而是你能不能绕过平均数陷阱找到中位数这个数学结论。顺带说一句如果题目改成一个经典变体“只能增加不能减少”那目标值就变成所有元素的最大值答案变成最大值与每个数的差之和思路就完全不同了。春招笔试里这种“操作类”题目反复出现核心其实是识别问题背后的数学结构而不是死记模板。3. Java实现排序取中位数一份能过笔试的写法3.1 完整实现代码import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine().trim()); String[] parts br.readLine().trim().split(\\s); long[] arr new long[n]; for (int i 0; i n; i) { arr[i] Long.parseLong(parts[i]); } Arrays.sort(arr); long target arr[n / 2]; long ans 0; for (long v : arr) { ans Math.abs(v - target); } System.out.println(ans); } }这段代码有几个细节值得讲讲。第一arr用的是long[]而不是int[]。虽然单个a[i]的绝对值可能只有10^9但排序后求|v - target|差值可能到2 * 10^9本身还在int范围内。可如果n是10^5累加结果最大能到2 * 10^14远超int上限。直接全部用long从头到尾不转型最省心。第二target取arr[n / 2]。Java 的整数除法向下取整n 4时取下标2n 5时取下标2正好是中位数或中间靠右那个数都没问题。第三Math.abs(long)返回long不会溢出。除非输入里有Long.MIN_VALUE这种极端值abs会溢出返回负数但校招笔试的数据范围基本不会这么刁钻不用过度担心。3.2 笔试环境下的Java效率细节我见过不少同学在笔试时用Scanner读数据n 10^5的时候其实还行但一旦数据量到10^6Scanner的解析开销就会让程序明显变慢而在线测评平台的Java时限通常给得很抠。所以在笔试里我一般建议直接用BufferedReader。它按行读入再手动split性能比Scanner高一个量级。有人还会用StreamTokenizer性能更强但代码可读性差现场写容易出低级错误我不推荐在笔试里用。另外还想提醒一句别为了省事把数组声明成Integer[]然后用Stream去排序。Arrays.sort(int[])用的是双基准快速排序而Arrays.sort(Integer[])用的是归并排序虽然都能过但基本类型数组少一层装箱拆箱时间上更稳。笔试环境求稳怎么简单怎么来。4. C实现用nth_element省掉一整个排序的耗时4.1 nth_element版完整代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } nth_element(a.begin(), a.begin() n / 2, a.end()); long long target a[n / 2]; long long ans 0; for (long long v : a) { ans llabs(v - target); } cout ans \n; return 0; }std::nth_element是 C 标准库里一个很容易被忽略的算法。它做的事情是部分排序保证第n/2个位置上的元素和整个数组完全排序后该位置的元素相同同时左边的元素都不大于它右边的元素都不小于它。它不保证整个数组有序但平均时间复杂度是O(n)比sort的O(n log n)少了一个log。这道题我们只需要中位数的值不需要完整有序数组所以nth_element在理论上是最优选择。数据量小的时候差距不明显但n到10^6量级能明显感受到差别。4.2 为什么乱序不影响最终计算有个同学问过我nth_element会打乱数组顺序那后面遍历a的时候元素还是原来的元素吗答案是肯定的。nth_element只做部分重排不删除也不复制整个vector里的元素还是原来的那一批只是位置变了。我们求答案时是遍历整个数组把每个元素跟target的差的绝对值加起来跟元素在原数组里的位置没有任何关系。所以乱序完全不影响最终结果。如果你在考场上不想用nth_element直接写sort(a.begin(), a.end())也完全能过。O(n log n)在10^5数据量下C 也就是几十毫秒的事。我的习惯是平时刷题用nth_element练手笔试现场反而常用sort因为人在紧张状态下越熟悉的代码越不容易出错。代码正确性永远比常数优化重要。还有一个细节C 里算绝对值我用的是llabs而不是abs。在bits/stdc.h全包含下abs(long long)也能编译但如果你只#include iostreamabs可能只匹配int版本导致长整数被截断输出就错了。llabs明确针对long long最省心。C11 及以上的std::abs已经重载了long long版本但为了兼容老平台我还是建议直接写llabs。5. Python实现代码最短但要注意读取和数据类型5.1 完整实现代码import sys def main(): data sys.stdin.buffer.read().split() if not data: return n int(data[0]) a list(map(int, data[1:1 n])) a.sort() target a[n // 2] ans sum(abs(v - target) for v in a) print(ans) if __name__ __main__: main()Python 的解法确实是最短的但越短越容易在细节上翻车。n // 2必须用整数除法不能用/。Python 3 里/得到的是浮点数拿浮点数当列表下标直接报TypeError。a.sort()是原地排序不返回值如果你写成a a.sort()那a就变成None了下一个循环直接崩。abs(v - target)在 Python 里天然支持大整数不存在溢出问题这对 Java 和 C 来说是个省心的优势。Python 的int是任意精度只要内存够随便算。5.2 读取方式与性能取舍我看到很多人在笔试里用input()一行一行读数据量小的时候没问题但n 10^5时逐行调用的累计开销就比较明显了。sys.stdin.buffer.read().split()把整个输入一次性读进来再按空白字符分割速度快非常多。如果你平时在力扣上写惯了函数式解题一上来容易写成def solve(a):然后等外部传参。但校招笔试系统里输入输出要完全自己处理这段read().split()的模板可以直接背下来用。有人担心 Python 跑10^5的排序会超时其实完全不用担心。Python 的sort是 TimSort混合排序10^5量级大概几十毫秒在线笔试轻松通过。如果n到了10^6Python 就会吃力但校招笔试第一题基本不会给这么大的数据。我还见过有人用statistics.median_low来取中位数不建议这样做。一是多引入一个标准库二是平台 Python 版本不定万一 API 行为有差异反而不如自己排序取下标可控。笔试环境里标准库越少依赖越好。6. 在线测试实践输入输出格式的自测技巧与常见误区6.1 单组样例与多组样例的判断进了在线笔试系统第一步不是写代码而是看输入描述。我见过太多人拿到题就写快写完了才发现输入是多组测试数据。单组数据的输入一般是这样的描述“第一行一个整数 n第二行 n 个整数”。多组数据则是“输入包含多组测试用例每组第一行为 n当 n 为 0 时结束”或者“输入有多组数据处理到文件末尾”。如果是多组数据C 的写法就变成while (cin n) { ... }Java 则是while (br.readLine() ! null) { ... }Python 用data sys.stdin.buffer.read().split()这种一次性读法天然支持多组数据只需要循环解析即可。但不管什么语言写代码前先花30秒确认输入格式能避免所有样例通过、提交全WA的尴尬。6.2 四个必测的边界数据在线测试最怕的不是算法错而是边界错。这道题我建议提交前至少跑这四组数据n 1数组只有一个数无论如何都不用操作答案必须是0。所有元素相等比如[5, 5, 5, 5]答案必须是0。全负数比如n 3, a [-5, -1, -3]排序取中位数-3答案是2 2 0 4。负数的绝对值处理最容易错尤其是某些语言里abs的坑。大数边界构造n 100000所有数都是10^9或-10^9验证答案会不会超出int范围。Java 和 C 选手如果用了int这里会直接溢出成负数一看输出是负的就知道该换long了。本地调试的时候我习惯把测试数据写进一个input.txt然后用重定向跑Javajava Main input.txtC./main input.txtPythonpython main.py input.txt这样比每次手动往终端里敲样例高效得多尤其适合反复验证边界数据。6.3 提交前最后检查一遍的清单线上笔试提交前我建议你过一遍这几个点每一项都曾经让真实考生翻过车Java 类名是不是Main在线测评系统基本都要求主类名为Main类名不对直接编译错误这是最常见的低级失误。C 有没有用long long答案类型不对数据一大就溢出。Python 的n // 2写没写对/会让列表下标直接报错。输出要不要带换行其实平台一般忽略末尾换行但用println或cout \n总没错。样例过了边界数据跑没跑尤其是n 1和全相等这两组。还有一个环境相关的建议如果你平时用的本地 IDE 是 VSCodeC 环境、Python 环境都要提前配好。笔试前三天别折腾环境别换编译器版本用你最顺手的那套配置。我见过有个同学在笔试当天更新了 VSCode 插件结果代码跑不起来了白白浪费半小时。考试这种事稳比什么都重要。最后分享一个我做这种题的习惯先写一版暴力枚举小数据的代码验证答案分布然后再用中位数思路去实现。比如这题你可以先枚举从min(a)到max(a)的所有整数作为目标值小数据量下暴力算一遍最优答案确认和中位数结论一致再放心提交。这样上线测试时底气会足很多。春招笔试不求炫技求稳、求快、求AC。祝大家都能顺利拿下面试邀请。