No.929 The Usual Ball-Moving Problem
タグ : / 解いたユーザー数 238
作問者 :
nmnmnmnmnmnmnm
/ テスター :
%20
Problem Statement
$N$ boxes are arranged in a row.
The $i$-th box from the left contains $B_i$ balls.
(When $B_i$ is 0, the box contains no balls.)
The total number of balls in all the boxes is $N$.
One operation consists of moving 1 ball from a box to one of the boxes adjacent to it on the left or right.
What is the minimum number of operations required so that every box contains exactly 1 ball?
Input
$N$
$B_0\ B_1\ \dots\ B_{N-1}$
$N$ is the number of boxes. $N$ is a positive integer. $1 \le N \le 100000=10^5$.
$B_i$ is the number of balls initially in the $i$-th box from the left.
$B_i$ is a non-negative integer. $0 \le B_i \le 100000=10^5$.
The sum of $B_0$ through $B_{N-1}$ is exactly $N$.
Output
Output the answer on one line.
Print a newline at the end.
Sample
Sample 1
Input
3 0 3 0
Output
2
There are 3 boxes, and the middle box contains 3 balls.
Of the 3 balls, move 1 to the box one to the left, and move 1 to the box one to the right.
Now every box has 1 ball. The number of operations required is 2.
Sample 2
Input
3 3 0 0
Output
3
Move 1 ball from the leftmost box to the box one to its right.
Move another ball from the leftmost box to the box one to its right.
Move 1 ball from the middle box to the box one to its right.
The number of operations required is 3.
Sample 3
Input
4 1 1 1 1
Output
0
No operations are needed.
Sample 4
Input
5 0 1 0 4 0
Output
5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。