解説

この問題では、目標とする比率$x$を定め、その比率を実現できるかどうかを判定する方法を取ります。この判定作業を効率よく行うために二分探索を用います。

まず、比率を$x$以上にできるかを考えてみましょう。数式で示すと以下のようになります。

$$\frac{\sum P_i}{\sum E_i} \geqq x$$

これを式変形していきます。平均最大化の考え方に近いと思います。

$$\begin{aligned} \frac{\sum P_i}{\sum E_i} &\geqq x \\ \sum P_i &\geqq x \sum E_i \\ \sum P_i - x \sum E_i &\geqq 0 \\ \sum (P_i - xE_i) &\geqq 0 \\ \end{aligned}$$

このように変形出来ます。よって、$k$個選んだ時、$(P_i - xE_i)$の総和が0以上になっていれば比率は$x$以上に出来ると判定できます。

証明は省略しますが、$(P_i - xE_i)$は大きい順に選ぶのが最適です。

計算量については、二分探索で$\log N$、判定でソートの部分が$N\log N$かかります。よって全体で$O(N (\log N)^2)$となります。

実装