ABC153 F. Silver Fox vs Monster
問題
N体のモンスターが一列に並んでいる。
i番目のモンスターは、座標x_iにいて、体力がh_iである。
今、爆弾を座標xに落とすと、x-D以上x+D以下の範囲にいるモンスターにダメージAを与えることができる。
すべてのモンスターの体力を0以下にするために必要な爆弾の個数の最小値を求めよ。
制約
- 1 <= N <= 2*10^5
- 0 <= D <= 10^9
- 1 <= A <= 10^9
- 0 <= x_i <= 10^9
- 1 <= h_i <= 10^9
解法
一番左にいるモンスターについて考えると、このモンスターを倒すためには、このモンスターを含む範囲の爆弾を倒すのに十分な回数落とす必要がある。
このモンスターの位置を左端とするような爆弾投下を十分な回数を透過したあと、次に一番左になるモンスターについても同様に考えていける。
したがって、貪欲法で、左から順番に処理していけば良い。
爆弾の投下によって、2*Dの範囲にいるモンスターに「A*投下回数」のダメージを与えることになるが、愚直にループを回すとO(N)かかってしまって間に合わない。
これは、遅延セグメント木やStarrySkyTree、imos法をしながら進めればO(logN)やO(1)で更新・取得ができる。
