和の比率の最大化
長さNの正の数列 Ai, Bi からK個選んでSとする。ABそれぞれの和の比率を最大化したいとする $ \argmax_S { \sum_{i\in S} B_i \over \sum_{i\in S} A_i }
和の比率を直接最大化するのではなく、和の比率がX以上かどうかの判定問題にし、Xを二分探索する解法がある
$ {\sum B_i \over \sum A_i} \ge X
$ \sum B_i \ge X \sum A_i
$ \sum B_i - X \sum A_i \ge 0
$ \sum (B_i - X A_i) \ge 0
条件を満たすSが存在するなら、$ B_i - X A_i が大きい方からK個選んだものは条件を満たす。
よってこの判定問題はO(NlogN)で解ける。
このXを二分探索すれば、条件を満たすSがある最大のXが求まる。これはXの最大値である。