はじめてのにぶたん(ABC 063-D)
二分探索とは...?
路頭に迷いましたNafmoです。
二分探索について書きたいと思ったので書きます
そもそもなんだそれ
要は、ソートされた列に真ん中からぶった切って
候補を半分ずつ減らしていく方法です
計算量はO(log N)らしい…
これを使えそうなものでかんたんに思いつくのが、
- 目的の値を探すこと
ソートしてあげて探せばできるね。
私はこの使い方しか知らなかったので
にぶたん問題の典型が解けなかったのですね。
今回の場合X回で倒しきれる、きれない。を判定してbool値を返せば、これについて単調性があるので探索できますね…
XXXOOOOOO
のような結果なら二分探索で境目が出せるってわけです。
(4番目がOの最小値)
OかXかを確認するのにかかる時間はO(N)(全部見ます)
二分探索は1～h[max]/Bまでなので、それにlogをつけた分だけ…
計算量的には間に合いますね。
- 値の判定だけでなく、境目の判定にも使える
そんなところでしょうか。
境目判定で最小値最大値を出せば解けるみたいな問題は考察して二分探索かどうか見てみるのも手だなと思いました。
(ABC 063 D-Widespread)
方針
X回で倒しきれるかどうかのJudge(int X)のようなものを作って、二分探索をかけます。
中身は h[i]-B*Xが0以下なら何もしない。以上なら(A-B)を何回与えれば0以下になるか調べる(この数の合計をTとする)
T>Xならfalse T<=Xならtrueを返しましょう
最後、止まった値がfalseなら1足すのをお忘れなく。
暇があれば...
追記をしていくよ(適当)
