ABC140 F Many Slimes
- 問題概要
始めの1つの値を決めた後、毎秒いま持ってる全ての値に対して、それより真に小さい値を手持ちに加える。最終的に与えられた配列A内の2^N個の数と一致させることができるか。
- 解法
現在持ってる値の配列をcurと呼ぶことにする。
配列A内で最大である要素を、一番最初の値にしなければいけないのは明らか。
さらに、cur[i]から生み出す値は、 Aの中でまだcurから生み出されていない値であってかつ、cur[i]より小さい値のうち最大のものが最適。これは、数が大きければ大きいほど、後で生み出せる数の範囲が大きくなるため。
したがって、貪欲による解法でOK。
ちなみに、curからは大きい順に取っていく必要はない。
実装は、既に生み出したものを削除するためにmultisetを用いた。
また、Aの値を全て負の値にすることで、multisetのメンバ関数のupper_boundが使いやすくなる。
