思路与算法

排序后用前缀和计算区间和。单元素价值为0，所以最优值非负。先证明只需考虑奇数大小的子集，再枚举其中位数位于排序数组的下标i。

若子集有2k+1个元素，中位数是a_i。固定i和k时，为使平均数尽量大，下半部应取a_i之前最大的k个，即a[i-k..i-1]；上半部应取全数组最大的k个，即a[n-k..n-1]。它们与a_i互不占用同一个下标，范围是0<=k<=min(i,n-i-1)。令S_k为这些2k+1项之和，价值g(k)=S_k/(2k+1)-a_i，S_k由两个前缀差O(1)取得。

增加到k+1时补入一对，和为c_k=a[i-k-1]+a[n-k-1]。随着k增大，c_k不增加。g(k+1)>g(k)当且仅当c_k*(2k+1)>2*S_k。这一改善条件一旦为假，后面不会再为真，形成有序的真前缀、假后缀。二分定位第一个不再改善的位置，得到该i的最优k。

所有平均数比较均用整数交叉乘法。最终最优值记为非负分数num/den，将其乘100000后用(2num100000+den)/(2*den)精确舍入，输出整数部分、小数点和补足五位的小数部分，不依赖浮点近似。

正确性说明

首先消去偶数子集。对一个2k项的子集，设和为S，中间两项为b<=c，中位数按通常定义为(b+c)/2，价值V=S/(2k)-(b+c)/2。分别删去b或c，得到两个2k-1项子集，它们的价值平均数为(2k/(2k-1))*V。若V>=0，至少一个删除后的奇数子集价值不小于V。由于全局最优至少为0，必存在不更差的奇数最优解。

任意奇数子集中，固定其中位数在完整排序数组中的下标i及半边数量k。下半部元素都在i之前，换成其中最大的k个不降低和且仍不超过a_i；上半部换成完整数组最大的k个，同样不降低和且仍不小于a_i。数量限制保证这些下标互异，中位数仍为a_i。故上述形状一定包含一个最优解，包括相同值重复出现的情况。

考察固定i。当前均值为A_k=S_k/(2k+1)，补入一对的均值为c_k/2。新均值是这二者的加权平均，所以它上升恰在c_k/2>A_k时。若某次不再上升，新均值位于c_k/2与A_k之间；下一对均值不大于c_k/2，因此下一次也不能上升。以后同理，严格改善谓词只能从真变假。二分准确找到其首次为假的边界，若始终改善则选择最大k，因此得到该i的最大价值。

枚举所有i覆盖所有奇数最优解，结合偶数化奇数结论得到全局最优。交叉乘法比较的是同一个精确有理数，最后整数舍入保证按五位小数输出目标值。

复杂度

排序O(N log N)，前缀数组分配与初始化O(N)，每个中位数的边界二分O(log(N+1))，每次只做常数次前缀求和。总时间O(N log(N+1))，额外空间O(N)。前缀和最多210^11，比较中的乘积和五位小数舍入中的乘积在约410^16以内，均使用long long。

易错点

1. 可重复数集表示输入中可有相等元素，每个输入位置最多选一次；不能无限重复使用某个数。
2. 上半部取全局最大的k个，下半部取中位数之前最大的k个，不是任意连续2k+1段。
3. 相等的中位数可能让不同i得到不同结果，必须枚举每个位置。
4. k=0对应单元素，价值0。边界K=0时无需访问额外一对，二分中点只在k<K时计算改善谓词。
5. 偶数中位数是中间两数的平均，消去偶数解的证明不能直接把下中位数当作原中位数。
6. 输出严格保留5位；不用浮点比较来决定峰位置。覆盖0、1000000、全部相同、重复中位数、极端两类频次和N=200000。

参考代码（C++11）

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n), pref(n + 1);
    for (ll &x : a)
        cin >> x;
    sort(a.begin(), a.end());
    for (int i = 0; i < n; ++i)
        pref[i + 1] = pref[i] + a[i];
    ll bestN = 0, bestD = 1;
    for (int i = 0; i < n; ++i) {
        auto sum = [&](int k) {
            return pref[i + 1] - pref[i - k] + pref[n] - pref[n - k];
        };
        int lo = 0, hi = min(i, n - i - 1);
        while (lo < hi) {
            int k = lo + (hi - lo) / 2;
            ll pair = a[i - k - 1] + a[n - k - 1];
            if (pair * (2LL * k + 1) > 2 * sum(k))
                lo = k + 1;
            else
                hi = k;
        }
        ll d = 2LL * lo + 1, num = sum(lo) - d * a[i];
        if (num * bestD > bestN * d) {
            bestN = num;
            bestD = d;
        }
    }
    ll rounded = (2 * bestN * 100000 + bestD) / (2 * bestD);
    cout << rounded / 100000 << '.' << setfill('0') << setw(5) << rounded % 100000 << '\n';
}