きままにものづくり

日々の気付いたことなんかを書いてます。

SRM631Div1Medium

問題

直線上のposition_i count_iの猫がいる。ひとつのpositionに複数の猫がいるのはよくないことである。猫は1秒に左右どちらかに1だけ移動できる。移動しないことも可能である。t秒後において、複数の猫が存在しなけばならないpositionの数を答えよ。

解法

貪欲法で解ける。
positionに対して昇順にソートする。猫を分散可能な場合は左から埋めていき、不可能な場合は全ての猫を右端に置く。次のpositionで以前右端に置いた箇所に到達可能ならば、そこに全ての猫を移す。

計算量

ソート: O(N log N)
探索: O(N)

コード

広告を非表示にする