ATCoder ABC334-C：奇数K时为何仅需尝试奇数索引元素？

问题背景 #

我是竞赛编程爱好者，最近在解ATCoder ABC334-C题时，把问题转化为从排序后的颜色序列$A_1,A_2,\ldots,A_K$中制作$\lfloor\frac{K}{2}\rfloor$对袜子的问题：

• 当K为偶数时，将排序后相邻元素配对（$(A_1,A_2),(A_3,A_4),\ldots,(A_{K-1},A_K)$）是最优策略，这点没问题。
• 当K为奇数时，我原本计划枚举每一只未配对的袜子，剩余元素按偶数K的方式配对，还用前缀和presum（比如presum[2] = A_2 - A_1，presum[4] = (A_4 - A_3)+(A_2 - A_1)）和后缀和把复杂度降到O(N)，但还是TLE了。后来看到题解里的优化：K为奇数时，只需要尝试跳过$A_1,A_3,A_5,\ldots,A_K$这些奇数索引的元素就行，完全不用考虑偶数索引的。我搞不懂为什么，另外我的LaTeX公式也没法正常显示，想请教解决办法。

一、为什么K为奇数时只需尝试奇数索引的袜子？ #

核心原因是排序后的序列是递增的，跳过偶数索引元素的代价一定大于等于跳过前一个奇数索引元素的代价，所以最优解不可能出现在跳过偶数索引的情况里。

举个具体例子，假设排序后的序列是$A_{i-2}, A_{i-1}, A_i, A_{i+1}, A_{i+2}$（i是偶数）：

• 如果跳过$A_i$（偶数索引），那么$A_{i-1}$只能和$A_{i+1}$配对，这一对的代价是$A_{i+1} - A_{i-1}$，加上前后其他配对的总代价。
• 如果跳过$A_{i-1}$（奇数索引），那么$A_i$和$A_{i+1}$配对，代价是$A_{i+1} - A_i$，加上前后其他配对的总代价。

对比两者的差值：$A_{i+1} - A_{i-1} = (A_i - A_{i-1}) + (A_{i+1} - A_i)$，显然比跳过$A_{i-1}$的代价多了$(A_i - A_{i-1})$（序列递增，这部分是正数）。所以跳过偶数索引的总代价必然更高，不可能是最优解。

再拿实际序列验证：比如K=5，序列是[1,2,3,4,5]。跳过偶数索引的2或4，总代价分别是3和3；而跳过奇数索引的1、3、5，总代价都是2，显然更优。

所以结论是：只需要枚举所有奇数索引的元素作为未配对的那只，就能找到最优解，这样枚举次数直接减半，从O(K)变成O(K/2)，就能避免TLE了。

二、LaTeX公式无法正常显示的解决办法 #

根据不同场景，解决方式不同：

• 本地编辑器（如VS Code）：安装支持LaTeX渲染的插件，比如「Markdown All in One」，然后在设置里开启「Enable Math Rendering」，就能正常解析$...$包裹的行内公式和$$...$$包裹的块级公式。
• 在线平台：先确认平台是否支持LaTeX，比如ATCoder题解区、知乎、CSDN都支持。如果还是不显示，检查语法：比如\lfloor和\rfloor这类命令是否正确，有没有漏写反斜杠；临时可以用[\frac{K}{2}]代替\lfloor\frac{K}{2}\rfloor（但竞赛场景尽量用准确符号，优先找支持完整LaTeX的环境）。
• 自定义页面：如果是自己写的网页，需要引入MathJax或KaTeX渲染库，比如在HTML里加一行MathJax的CDN链接，就能自动解析LaTeX公式了。

内容的提问来源于stack exchange，提问作者singleslit