61-A

61-A

题目叙述

求一堆数的平均值-中位数最大是多少。

题解

考虑枚举中位数是多少，那么只要比中位数大的选若干个，小的选若干个就行了。

现在有这样一个事实：答案一定不是选择长度为偶数的序列。这是一件非常有意思的事情。只要证明，如果现在有一个集合大小为偶数，就能找到比他权值更大的集合。可以这样证明：

设这个序列为 (a_1,a_2,cdots,a_n,a_{n+1},cdots,a_{2n}) ，那么考虑去掉 (a_n) 或者去掉 (a_{n+1}) 后的结果。如果设前 (n) 个数的和为 (s_0) ，后 (n) 个数的和为 (s_1) ，那么去掉 (a_n) 和去掉 (a_{n+1}) 后的平均数-中位数为 (frac{s_0-a_n+s_1}{2n-1}-a_{n+1}) 和 (frac{s_0-a_{n+1}+s_1}{2n-1}-a_n) 。原本的平均数-中位数为 (frac{s_0+s_1}{2n}-frac{a_{n}+a_{n+1}}{2}) 。可以发现，在 (s_0+s_1ge n(a_n+a_{n+1})) 的时候 (frac{s_0-a_n+s_1}{2n-1}-a_{n+1}+frac{s_0-a_{n+1}+s_1}{2n-1}-a_nge2(frac{s_0+s_1}{2n}-frac{a_{n}+a_{n+1}}{2})) 。那么也就是说去掉 (a_n) 和去掉 (a_{n+1}) 后的结果中必有一个比原本的大。而如果这两个都没有原本的大，那么说明 (s_0+s_1ge n(a_n+a_{n+1})) ，也就是说 (frac{s_0+s_1}{2n}-frac{a_{n}+a_{n+1}}{2}) 是个非正数，而我只选择一个数 (a_0) 一定至少是 0，所以偶数序列就必然不会对答案做出贡献。

剩下问题就变成，枚举奇数后如何计算答案了。首先一定是从大到小选，其次可以发现，选着选着到了某个数之后再选平均数就会下降，在这之前平均数就会增加。这是一个非常有意思的事情。可以这样解释：

考虑先选择了一个中位数，如果中位数是 (z)，那么可以用点 ((1,z)) 表示目前的状态。原点与这个点的连边的斜率就是平均数。多选择两个数，就变成了 ((1+2,z+x_0+x_1)) 。每次选的数是单调递减的，所以这是一个凸包。那么就是说，凸包顶点与原点斜率最大的地方就是答案。这个很明显可以二分，因为凸包上的点与原点形成的斜率很明显是先增再减的。