[AtCoder] ARC 006 C – 積み重ね

問題

方針

山 \( i \) に積まれている一番上の重さを \( v_i \) とします。初期値は、\( v_1 = w_1 \) です。段ボール \( j \) が全ての山に対して \( v_i < w_j \) を満たすとき、新しい山を作ります。そうではないとき、\( v_i \geq w_j \) を満たす \( i \) に対して、\( v_i – w_j \) を最小化する山を見つけます。そして、\( v_i \leftarrow w_j \) と更新します。

段ボール \( i \) を載せられる山があるにもかかわらず、新しく山を作る方法がなぜダメかというと、コスト \( 1 \) 増えるのと同時に、許容量が \( w_i \) の山が新たにできます。新しく山を作らなければ、コストが増えずに、許容量が \( w_i \) の山ができます。

コード