二分探索:その他(2題)
プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~
この本(通称:蟻本)の章末で紹介されている練習問題をひたすらといている。
二分探索。その他。
POJ1759: 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
解法
POJ-3484, LiveArchive-3834, ZOJ-3117, SPOJ-MSE07E : Showstopper - komiyamの日記
これを見た。WA を連発した。