すべて、 \(A\) の平均値 \((=\mu)\) にすることで \(A\) の値を等しくしていきます。

\(A\) の総和を \(N\) で割り切れない場合は不可能であるため \(-1\) を出力します。

また、途中で値が足りずに平均値にできない場合(操作の途中で \(A_1=...=A_i=\mu, A_{i+1}<\mu\) となる場合)も不可能です。

すべて等しくすることが可能な場合、平均値との差の値をずらしながら操作をしていきます。 (操作はすべて最小になります)

具体的には、以下の4つのステップで答えを求めることができます。

1. 数列の平均値 \(\mu = \frac{1}{N}\sum_{i=1}^N A_i\) を計算する

(割り切れない場合、すべての値を等しくできないため \(-1\) を出力し、終了する)

1. 各要素と平均値の差 \(b_i = A_i - \mu\) を計算する

2. \(b_i\) の累積和 \(S_i = \sum_{j=1}^i b_j\) を計算する

3. \(\sum_{i=1}^N S_i\) を出力する

(ただし、 \(S_i \lt 0\) を満たす \(i\) が一つでもある場合は \(-1\) を出力する)

計算量は \(O(N)\) です。

クレジット

原案： S0ni

解法： S0ni

問題準備・解説： US_cube

レビュー： Jinapetto

テスター： physics0523

校正： nu50218