[Codeforces] Codeforces Round #668 (Div. 2) B. Array Cancellation

2020年9月8日

問題

方針

\( i < j \) のとき、\( a_i \leftarrow a_i – 1 \)、\( a_j \leftarrow a_j + 1\) という操作は \( 0 \) コストでできますが、\( i > j \) ではコストが \( 1 \) かかります。

前から順番に調べていき、\( a_i > 0 \) となる \( a_i \) の和を \( s \) とします。\( s \) が正であれば、\( a_i < 0 \) となる要素にたいして \( s \) までコストが掛からずに操作を行うことができます。

\( a_i < 0 \) のとき

\( a_i + s \geq 0 \) ならばノーコストで \( a_i = 0 \) とすることができます。また、\( s \leftarrow a_i + s \) と更新します。\( a_i + s < 0 \) のとき、\( -(a_i + s)\) のコストを払い \( a_i = 0 \) とすることができます。また、\( s = 0 \) となります。

\( a_i \geq 0 \) のとき

\( s \leftarrow a_i + s \) と更新します。

コード