No.929 よくあるボールを移動するやつ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 133
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm / テスター : %20%20
4 ProblemId : 2255 / 出題時の順位表
問題文最終更新日: 2019-11-20 00:24:52

問題文

$N$個の箱が1列に並んでいます。
左から$i$番目の箱にはボールが$B_i$個入っています。
($B_i$が0のときにはボールは入っていません。)
すべての箱に入っているボールの数の合計は$N$個です。

ある箱の左右のいずれか1つ隣の箱に1個のボールを移動させるのを1つの操作とします。
全ての箱に1個ずつボールが入っているようにするためには最少で何回の操作が必要か?

入力

$N$
$B_0\ B_1\ \dots\ B_{N-1}$

$N$は箱の個数。$N$は正の整数。$1 \le N \le 100000=10^5$。
$B_i$は左から$i$番目の箱に最初から入っているボールの数。
$B_i$は負でない整数。$0 \le B_i \le 100000=10^5$。
$B_0$から$B_{N-1}$までの合計はちょうど$N$になる。

出力

答えを1行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
0 3 0
出力
2

3つの箱があって真ん中の箱にボールが3個入っています。
3つのうち1つを1つ左の箱に移動、1つを1つ右の箱に1個移動します。
これで全ての箱に1つのボールがあります。必要な操作回数は2回です。

サンプル2
入力
3
3 0 0
出力
3

いちばん左の箱のボールを1つ右の箱に移します。
いちばん左の箱のボールをもう1つ右の箱に移します。
真ん中の箱のボールを1つ右の箱に移します。
必要な操作回数は3回です。

サンプル3
入力
4
1 1 1 1
出力
0

操作は必要ありません。

サンプル4
入力
5
0 1 0 4 0
出力
5

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。