ABC172 C - Tsundoku - uniの競プロlog

問題リンク

解法

答えを二分探索する。
「 $X$ 冊読めるか」の判定は、事前に累積和を取り「机Aの本を $i$ 冊読むための所要時間」(Bも同様)を求めれば、机Aで $i$ 冊、机Bで $(X-i)$ 冊読むとしてそれぞれの所要時間の和が $K$ 以下かどうか判定すれば良い。
判定は $O(1)$ で行うことができ、 $i$ の全探索で $O(N)$ 、答えの範囲は $0$ 以上 $(N+M)$ 以下なので二分探索で $O(\log(N+M))$ 、よって全体の計算量は $O(N\log(N+M))$ となる。