ARC021 C - 増築王高橋君
問題
解法
最小費用で増築するためには，現段階で費用が最小の建物を毎回選んで増築し続ければ良いことがわかる． しかし，毎回すべての建物の費用を確認すると計算量がO(KN)となり，40点しか得られない．
満点解法
貪欲法で増築する建物を選び続けたと仮定して，K回目の増築にかかる費用をPとする．
各建物の増築にかかる費用Piは，
となり，費用Pに達するまでに
Xi回増築を行うことができる．この操作はO(1)で行える．
Pはを満たす最小の値を2分探索で求める．
Pが求まれば，後は各建物の増築費用を足していくだけ．
建物の増築費用PiがPと等しい場合は余分に料金が足される場合があるので，最後に引いてやる必要がある．
計算量はO(NlogL)(LはPの最大値: 1012ぐらい?)
