二分探索:その他(2題)

プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~
この本(通称:蟻本)の章末で紹介されている練習問題をひたすらといている。

二分探索。その他。

POJ1759: Garland

1759 -- Garland

問題概要

次の制約によって N 個のランプを取り付ける。H[i] はランプ i の高さである。
H[1] = A
H[i] = (H[i-1] + H[i+1])/2 - 1, for all 0 < i < N
H[i] >= 0, for all 0 <= i <= N
このとき、B = H[N] の最小値を求める。
3 <= N <= 1000
10 <= A <= 1000

解法

H[1] は与えられているので、H[2] が決まればあとは H[N] まで全部決まるし、途中で H[i] < 0 になれば H[2] の値が不適切だということもわかる。そこで、H[2] の最小値を二分探索で求めて、それから H[N] を計算すればいい。


POJ3484: Showstopper

3484 -- Showstopper