No.929 よくあるボールを移動するやつ
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 229
作問者 :
nmnmnmnmnmnmnm
/ テスター :
%20
タグ : / 解いたユーザー数 229
作問者 :
nmnmnmnmnmnmnm
/ テスター :
%20
問題文最終更新日: 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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。