ABC014C 節制 - ゆるふわ競プロ

2分岐探索

atcoder.jp

問題概要

N日満腹度が0より大きい状態でいる.毎日以下の3つの行動のいずれかをする

代金a円払いbの栄養をえる
代金c円払いdの栄養をえる
栄養を e 失う

この状況下で生き残るために払う最初の値段を求める

考え方

最初に栄養をとり残りの日数で干からびていく動作を行うようにする.
1と2と3を行う操作の合計回数は日にちのN回になる.
1. を行う操作をした時に最低2を何回すれば良いかを求める.
2を何回行うかを求める際に2分岐探索を使う。

キーコード

i : 普通の食事の回数
while文で2分岐探索を行なっている
left = -1から始めているのはなぜだろう
-1 ではなく 0 に初期化した時には WA になってしまった.

なぜleft = -1なのか

考えてみたらそれはそうって感じでした.while文の条件が(right - left > 1)になっています.終了条件としては,

   left + 1 = right

となりますこの終了条件を満たした時に実際に計算に使われる数字はrightの方です. left を-1 ではなく 0 で初期化してしまった場合何が起こるかというと,rightが 0 になることがありません 0 + 1 の 1が最小値となってしまいます.そのためleftは-1で初期化します.

for (int i = 0; i <= n; i++) {
            // i : 普通の食事回数
            // 普通食事をしないひの中で２分岐探索
            long right = n - i;
            long left = -1;
            while (right - left > 1) {
                long mid = (left + right) / 2;
                if (b * i + d * mid + h - (n - mid - i) * e > 0) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            long cost = a * i + right * c;
            ans = Math.min(ans, cost);
        }

参考

ACコード