方針については 公式解説 と同じです。

決め打ちした値を \(p/q\) とおくと、条件を満たす添字の集合 \(S\) に対して \(\sum_{i∈S} (a_i - p/q) \gt 0\) とできるかを判定すればよいです（そうできない最小値が、求める平均値）。すなわち、\(\sum_{i∈S} (qa_i - p) \gt 0\) です。

さて、求める平均値は \(n\) 個以下の正整数の平均値なので、既約分数の形で書けば分母は \(n\) 以下となります。 よって、Stern–Brocot tree 上で二分探索すればよく、厳密値を既約分数の形で \(O(n\log(n))\) 時間で求められます。

関連リンク

• 提出 #40898345
• 解説ブログ