穿回初中的我，今天在给语文题写复杂度分析
昨天那波操作让我一战成名——全班都知道了李码同学不仅会手搓空气，还能用"欧几里得算法"秒杀数学题。
今天，王老师又把我叫到了办公室。
“李码啊，你数学这么厉害，语文应该也不差吧？”王老师露出了一种产品经理似的微笑，“今天下午有个’大型跨学科阅读理解比赛’，你去代表我们班参加一下。”
我心里咯噔一下：“王老师，我是纯正理科生，写作文只会用分号的那种……”
“欸，”他大手一挥，直接打断我的报错信息，“素质教育，要全面发展！”
说着，他从抽屉里抽出一张报名表，上面赫然印着——第一届"文曲星"杯跨学科阅读理解大赛。
“再说了，题干看不懂，算法再牛有什么用？你昨天的推导，逻辑清晰，抓重点准——这不就是阅读理解的核心能力吗？” 王老师把报名表塞到我的手里。
我张了张嘴，竟然找不到任何逻辑漏洞来反驳——这不科学，他的推理链居然在语义层面自洽了。
下午两点，学校阶梯教室。
我坐在最后一排，看着台上挂着的横幅：“第一届’文曲星’杯跨学科阅读理解大赛——高手过招，笔上见真章”。台下坐满了各班的种子选手，一个个正襟危坐，手里攥着2B铅笔，眼神里透着"我刷过五年真题"的杀气。
主持人是语文组的张老师，她推了推金丝眼镜，笑眯眯地说：“同学们，今天的比赛题目非常特别，它不仅考验你们的阅读能力，还考验你们的逻辑思维能力。请大家看大屏幕——”
题目打出来的那一刻，我以为自己出现了幻觉。
【阅读下列文字，回答文后问题】
数对的最大公约数之和
给定一列整数，我们可以按照下面的步骤，得到一个特殊的总和。 第一步，从左到右依次处理每个数。对于当前位置，先找出从起始到这儿出现过的最大值，然后拿着当前这个数，和刚才找出的那个最大值，计算它们的最大公约数。这样按顺序生成的每一个最大公约数，就组成了一个新列表，我们暂且称它为“前缀最大公约数列表”。 第二步，把前面得到的“前缀最大公约数列表”里的所有数字，按照从小到大的次序重新排列。 第三步，观察重新排列后的列表。如果列表的长度是奇数，说明正中间有一个元素落单了——这个中间元素将不再参与后面的环节，直接放到一边，不予理会。 第四步，对于剩下的数字，采用“头尾结对”的方式配对：每次都从还没配对的数字里，挑出最小的那一个和最大的那一个，让它们组成一对。重复这个操作，直到所有的可配对数字都配成了对儿。 第五步，对刚才组成的每一对数字，求出它们的最大公约数。然后把所有这些“数对的最大公约数”加在一起，得到的总和，就是最终的答案。
请阅读上述材料，完成下面的问题。 现有整数序列：
[6, 10, 3, 12, 4]。请你依据短文所述规则，计算出最终的输出结果。
我读完第一遍，脑子里只有一个念头：这真的不是某个变态OJ的题库泄露了？现在的教育已经卷到这个地步了？
我环顾四周，发现其他选手已经开始动笔了。前排的学霸女生眉头紧锁，正在认真地画圈圈；隔壁班的体育委员抓耳挠腮，看起来想把卷子吃了。
我又读了一遍题目。以及，又读了一遍题目。第三遍读完，我终于悟了——这不就是把一个数组先这样、再那样、然后头尾结对，再把每对共同点加一起吗？
这哪是考语文，这分明是考“在自然语言的迷雾中还原抽象逻辑”的能力。
我从笔袋里抽出一支圆珠笔，决定人肉编译。
第一步：解析题意（相当于阅读 API 文档） 这题给了数组 nums，要先造一个 prefixGcd 数组。 定义很绕，但核心就一句：对于每个位置 i，先找到从开头到这里的最大值 mxi，然后计算 gcd( nums[i] , mxi )，得到一个新数组 prefixGcd。简单说，就是每个位置的原数和前缀最大值求个最大公约数。
第二步：硬跑 prefixGcd
题目给的序列是 [6, 10, 3, 12, 4]。从左到右，一边走一边维护“前缀最大值”，然后和当前数求最大公约数。
- i = 0：当前数 6，到这儿为止的最大值是 6，gcd(6, 6) = 6
- i = 1：当前数 10，前缀最大值更新为 10，gcd(10, 10) = 10
- i = 2：当前数 3，前缀最大值还是 10，gcd(3, 10) = 1 —— 3 和 10 互质，公约数只有 1
- i = 3：当前数 12，前缀最大值更新为 12，gcd(12, 12) = 12
- i = 4：当前数 4，前缀最大值还是 12，gcd(4, 12) = 4
于是prefixGcd = [6, 10, 1, 12, 4]。
我在纸上写下这串数字，旁边批注了一行：“时间复杂度 O(n)，空间复杂度 O(n)。” ——我不禁怀念起我的 IDE，一个 for 循环加上 max_val = max(max_val, num) 就搞定了，但现在我只能手动模拟。
第三步：排序
把 [6, 10, 1, 12, 4] 从小到大排列。这步在代码里一行 Arrays.sort() 就完事了，但我现在得人肉冒泡——还好只有五个数，我直接瞪眼法：[1, 4, 6, 10, 12]。
第四步：头尾结对
排好序的数组是 [1, 4, 6, 10, 12]，长度是 5，奇数，中间是 6。按规则，正中间那个元素直接忽略。可怜的 6，站 C 位却只能当观众。剩下待配对的：[1, 4, 10, 12]。规则是每次挑最小的和最大的凑一对：
- 最小 1 与 最大 12 配对 → (1, 12)
- 次小 4 与 次大 10 配对 → (4, 10)
第五步：求每对的 gcd 并求和 对 (1, 12) ：gcd(1, 12) = 1 —— 1 和任何数的最大公约数都是 1。 对 (4, 10) ：gcd(4, 10) = 2 —— 4 和 10 的最大公约数是 2。 把结果加起来：1 + 2 = 3。
我在草稿纸上画了个大大的圈，圈里端端正正写了个 3。
但我的手依然没停下——职业病发作，我忍不住在答案旁边画了一串框图：nums → prefixGcd → sort → 首尾配对 → 求 gcd → 累加 → 结果。
画完之后想了想，又补了一行小字：“总时间复杂度 O(n log n)，瓶颈在排序。如果允许用桶排序可以压到 O(n)，但这里 n=5，属于过度优化的职业病，不建议在实际考试中展示。”
交卷的时候，我看到前排的学霸女生还在检查第三遍，她看我的眼神里写着：“你这么快交卷，是不是瞎写的？” 而体育委员已经把卷子折成了一架纸飞机，正准备朝窗外发射。
张老师接过我的卷子，先习惯性地扫了一眼答案，然后目光被边边角角那些乱七八糟的批注吸引了——“O(n log n)”、“桶排序”。她摘下眼镜擦了擦，重新戴上，表情就像那个地铁老人看手机的表情包。
“李码同学，”她压低声音，“你这些……注释，是什么意思？”
“哦，那个啊，”我抓了抓后脑勺，“就是对解题思路的一种……呃，元认知层面的反思。属于阅读理解的高级技巧——不仅读懂文本，还能审视自己的理解过程。”
张老师沉默了三秒，在卷子上打了个勾，把卷子放到一边。
走出阶梯教室，阳光晃眼。同桌瘦猴冲过来：“李码！怎么样？难不难？”
我拍了拍他的肩膀：“兄弟，这么说吧——就是用语文的形式包装了一道算法题：
- 先算每个数和它前面最大值的 GCD，就像是在计算你和咱班最高分的默契度
- 然后把结果从小到大排个序
- 最小的和最大的配对，中间有落单的就忽略
- 算出每一对有多少 GCD，全加起来
简单搞定！”
瘦猴愣了五秒：“你能不能说人话？”
“我已经说了啊。”
“你这叫人话？”
我正准备回怼，忽然看见走廊那头，隔壁班的英语课代表从阶梯教室的门口走过。午后的阳光从窗户斜斜打进来，在她的马尾辫上镀了一层金色的光圈。她正低着头走路，嘴角带着一丝若有若无的弧度——那种刚做完一道难题、自我感觉良好的微笑。
“哎哎哎，”瘦猴在旁边疯狂挤眼睛，“别看了，别看了，人家都走过去了！”
“我在想算法，你想什么呢？”
“你脸都红了，算法叫’脸红’是吧？还是叫’心跳加速排序’？”
我决定下次他要再问问题，先收费。
彩蛋：
这道题其实就是纯模拟，关键是把题目描述的每一步拆解清楚：
Step 1：构造 prefixGcd 数组
- 维护一个 running max（当前最大值）
- 对每个位置 i，计算 gcd(nums[i], max_so_far)
Step 2：排序
- 直接 sort()，O(n log n)
Step 3：配对求和
- 双指针：左指针指向最小，右指针指向最大
- 每次取 gcd(left, right) 累加到结果
- 循环 n//2 次（向下取整，自动处理奇数情况）
完整代码：
n = len(nums)
prefixGcd = [0] * n
max_num = 0
# 第一步：构造 prefixGcd
for i in range(n):
max_num = max(max_num, nums[i])
prefixGcd[i] = gcd(nums[i], max_num)
# 第二步：排序
prefixGcd.sort()
# 第三步：最小配最大，求和
result = 0
for i in range(n // 2):
result += gcd(prefixGcd[i], prefixGcd[-1-i])
return result
复杂度分析：
- 时间复杂度：O(n log n)，瓶颈在排序
- 空间复杂度：O(n)，需要额外数组存储 prefixGcd
对于 n ≤ 10^5 的数据规模，完全够用。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。