AtCoder Regular Contest 075 D - Widespread

arc075.contest.atcoder.jp

魔物の体力s[1]～s[N]が与えられる。一回の魔法攻撃で、特定の一つの魔物の体力をA削り、その他すべての魔物の体力をB削る。ただしA>Bとする。全滅させるには魔法攻撃を最低何回打てばよいか？

C=A-Bとする。魔法攻撃の回数をkとした時、すべての魔物は少なくともkBの体力が削られている。s[i] - kB > 0 であるような各iについて、(s[i] - kB) / C (ただし切り上げ)を計算して和を取ると、その敵に対してAの攻撃を何回当てれば体力が0になるかが算出される。この回数の合計がkより少なければ少なくともk回の魔法攻撃では魔物の全滅させることが可能である。そこで、kを二分探索する。O(N log(max(s[i]))。