# 最接近中位数的数

**出题人解法：** 用选择算法求中位数，再按距离与数值的组合顺序选择前 $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 位范围内。

[排序后从中间向两侧合并](solution-alternative.zh.md)提供确定的 $O(n\log n)$ 时间和直观的有序结构，代码见[补充程序](alternative.cpp)。两份程序都通过当前完整配方；首选保留出题人的平均线性算法。

## 实现与验证

[标准程序](std.cpp)、[生成器](tests/generate.py)、[测试配方](tests/plan.json)。

参考环境中标准程序最慢中位数 0.115108 秒，峰值 12.81 MiB，校准时限 0.5 秒。每例独立运行五次。

[评测环境](../../../docs/评测环境与性能.md)与[逐次时间和哈希](../../../docs/benchmark-R31.json)。数值只适用于所记录环境，迁移评测机需重新校准。