蟻本の練習問題埋め3-1(1)

蟻本

二分探索（最小値の最大化）
二分探索における現在の区間の中央の値をxと表す。

POJ 3258 - River Hopscotch

http://poj.org/problem?id=3258
石の位置をソートして答えで二分探索。
幅がx未満になるような場合、その石を除くようにする。

POJ 3273 - Monthly Expense

http://poj.org/problem?id=3278
答えで二分探索。
和がxを超えるようなら分割する。

POJ 3104 - Drying

http://poj.org/problem?id=3104
答えで二分探索。
乾燥機に入れたらその秒に減る水の量はkでk+1でないことに注意。

POJ 3045 - Cow Acrobats

http://poj.org/problem?id=3045
牛iと牛jどちらを下にしたほうが得かを考えると、s[i]+w[i]が大きい方を下にしたほうがいいことがわかる。
よってw[i]+s[i]でソートして並べる。
二分探索解あるのかな…