arc021_3
C - 増築王高橋君
https://gyazo.com/0cedd265db86638eaab777a64ed378a5
考えたこと
Kが小さければコストの安い方から貪欲に取っていけば良い、しかしKは10^8
「安い方から」ということは、選択した中で最も高いxが存在する
各建物ごとにx以下で可能な増築は定数オーダーで求められる
なので「x以下で可能な増築の総量f(x)」は10^5オーダーで求まる
f(x)がKになる最小のxを二分探索でまとめれば良い
最大化を二分探索で
。今回は最小化だけど。
公式解説OK