题解

思路

把 $A$ 升序排序。

做法

对任意一个子序列，加入一个不大于当前平均值的未选元素不会降低得分；若已选的某个高于平均值的元素还能换成更小但仍高于平均值的未选元素，替换后平均值下降，得分同样不会降低。反复进行这些调整，可知一定存在一个最优子序列恰好是排序后数组的某个前缀。

依次枚举前缀长度 $k$ 并维护前缀和 $s$。前缀中的整数 $A_i$ 严格大于平均值 $s/k$，等价于 $A_i>\lfloor s/k\rfloor$；在当前前缀中二分找到最后一个不超过该值的位置，就能得到得分。

复杂度

每组数据时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。