CodeForces #262_Div2 : C. Present
問題
n個の連続した整数があり、m回大きさwの区間の要素を1増やす事ができる。
最も小さい要素を最大化させたい。
解法
二分探索で最も小さい花の高さをmid以上にできるか判定し最大値を探索する。
大きさnの配列を舐めながら、高さがmid未満の花があれば差分の水を足し、
足した箇所からw先まで花の高さを底上げすることができる。
(配列を用いて水を足したindexからw離れたら足した分を引くように処理する)
途中で水を足した総数がmを超えたらfalseを返しmidを小さい方に寄せる。
計算量は。
シンプルで結構好きな問題。
