最接近中位数的数¶
出题人解法： 用选择算法求中位数，再按距离与数值的组合顺序选择前 \(k\) 项。Codex（GPT-6）贡献： 原地保存数值、64 位安全计算、补充排序合并方案与验证。
两次选择¶
令 \(T=2m\) .奇数长度时，它等于中间值的两倍；偶数长度时，它等于两个中间值之和。调用 nth_element 得到零基下标 \(\lfloor n/2\rfloor\) 处的值；偶数长度再取它前面部分的最大值，就是另一个中间值。
比较两个数时，先比较 \(|2a_i-T|\) ，再优先选择较大的 \(a_i\) .这与先比较 \(|a_i-m|\) 再按数值打破平局完全等价，而且不需要浮点数。
按此比较器再次调用选择算法，使前 \(k\) 项为所需元素，然后求和。\(k=n\) 时直接对全部元素求和，不需要第二次选择。
正确性¶
第一次选择的分区性质保证中间秩的值正确，偶数情况下左半最大值正是下中位数。故 \(T\) 正确。将所有距离乘以正数二不改变顺序，比较器的第二关键字也与题意一致。因此第二次选择得到的前 \(k\) 项恰好是题目要求的多重集合；重复同值的相对顺序不影响答案。求和即为正确输出。
复杂度与数值¶
标准库选择算法平均线性，整个方案平均时间 \(O(n)\) .输入数组占 \(O(n)\) 空间；辅助空间取决于所用标准库的选择实现，此程序不另建距离数组。不要将 nth_element 的平均线性保证写成最坏线性保证。
使用 64 位保存 \(T\) 、距离和答案。绝对距离可能接近 \(4\times10^9\) ，答案绝对值小于 \(10^{15}\) ，均在 64 位范围内。
排序后从中间向两侧合并提供确定的 \(O(n\log n)\) 时间和直观的有序结构，代码见补充程序。两份程序都通过当前完整配方；首选保留出题人的平均线性算法。
实现与验证¶
参考环境中标准程序最慢中位数 0.115108 秒，峰值 12.81 MiB，校准时限 0.5 秒。每例独立运行五次。