条件を満たすように $X$ 匹選ぶことが可能であるとします。このとき、ある微生物 $i$ で、 $a_i$ が選んだ $X$ 匹の $a$ の平均以上となるものが必ず存在します。このとき、微生物 $i$ を取り除いても平均が増えることはなく、選んだ微生物の $b$ の最小値が減ることはないので、このときも条件を満たします。よって、条件を満たすように $X-1$ 匹選ぶことが可能です。
これより、解には単調性があることがいえるので「条件を満たすように $X$ 匹選ぶことが可能か」という問題が解ければ二分探索によりこの問題を解くことができます。以降はこの小問題を考えます。

さて、 $b_1 \leq b_2 \leq \cdots \leq b_N$ として一般性を失いません。ここで、選ぶ微生物の番号で最小のものを $K$ とするとき、小問題は「 $a_{K+1}$ から $a_N$ まで $X-1$ 個選んで総和を $b_K \times X - a_K$ 以下にできるか」と言い換えることができます。
これはC++ならば要素が大きいものが前に来るpriority_queueに $i$ の大きい順に $a_i$ を入れていき、大きさが $X-1$ を超えたらpopするという方針において、現在priority_queueに入っている値の総和を変数として管理しておくことで $K$ が大きい順に判定していくことができます。
これより、小問題は $O(N \log N)$ で解くことができました。

答えが \(N\) を超えることはないので、小問題は \(O(\log N)\) 回解けば十分です。よって、この問題は \(O(N (\log N)^2)\) で解くことができました。