/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
高橋君は次の 2 種類の操作のうち 1 つを選んで行う事を、何回でも (0 回でも良い) 繰り返し行う事ができます。
- 1\leq i\leq N-1 をみたす整数 i を選び、A_i を 1 減らし、A_{i+1} を 1 増やす。
- 1\leq i\leq N-1 をみたす整数 i を選び、A_i を 1 増やし、A_{i+1} を 1 減らす。
数列 A が次の条件をみたすようにするために必要な操作の回数の最小値を求めてください。
- 任意の 1 以上 N 以下の整数の組 (i,j) に対して、\lvert A_i-A_j\rvert\leq 1 が成り立つ。
制約
- 2 \leq N \leq 5000
- \lvert A_i \rvert \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
数列 A が問題文の条件をみたすようにするために必要な操作の回数の最小値を一行に出力せよ。
入力例 1
3 2 7 6
出力例 1
4
次のようにして 4 回の操作で A が条件をみたすようにできます。
- i=1 を選び、A_1 を 1 増やし、 A_2 を 1 減らす。A=(3,6,6) となる。
- i=1 を選び、A_1 を 1 増やし、 A_2 を 1 減らす。A=(4,5,6) となる。
- i=2 を選び、A_2 を 1 増やし、 A_3 を 1 減らす。A=(4,6,5) となる。
- i=1 を選び、A_1 を 1 増やし、 A_2 を 1 減らす。A=(5,5,5) となる。
この時操作回数が最小であり、よって 4 を出力します。
入力例 2
3 -2 -5 -2
出力例 2
2
次のようにして 2 回の操作で A が条件をみたすようにできます。
- i=1 を選び、A_1 を 1 減らし、 A_2 を 1 増やす。A=(-3,-4,-2) となる。
- i=2 を選び、A_2 を 1 増やし、 A_3 を 1 減らす。A=(-3,-3,-3) となる。
この時操作回数が最小であり、よって 2 を出力します。
入力例 3
5 1 1 1 1 -7
出力例 3
13
うまく操作することで、13 回の操作の後で、 A=(0,0,-1,-1,-1) にでき、これは問題文の条件をみたします。 12 回以下の操作で条件をみたすようにすることはできないため、13 を出力します。
Score : 550 points
Problem Statement
You are given an integer sequence of length N: A=(A_1,A_2,\ldots,A_N).
Takahashi can perform the following two operations any number of times, possibly zero, in any order.
- Choose an integer i such that 1\leq i\leq N-1, and decrease A_i by 1 and increase A_{i+1} by 1.
- Choose an integer i such that 1\leq i\leq N-1, and increase A_i by 1 and decrease A_{i+1} by 1.
Find the minimum number of operations required to make the sequence A satisfy the following condition:
- \lvert A_i-A_j\rvert\leq 1 for any pair (i,j) of integers between 1 and N, inclusive.
Constraints
- 2 \leq N \leq 5000
- \lvert A_i \rvert \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print a single line containing the minimum number of operations required to make the sequence A satisfy the condition in the problem statement.
Sample Input 1
3 2 7 6
Sample Output 1
4
You can make A satisfy the condition with four operations as follows.
- Choose i=1, and increase A_1 by 1 and decrease A_2 by 1, making A=(3,6,6).
- Choose i=1, and increase A_1 by 1 and decrease A_2 by 1, making A=(4,5,6).
- Choose i=2, and increase A_2 by 1 and decrease A_3 by 1, making A=(4,6,5).
- Choose i=1, and increase A_1 by 1 and decrease A_2 by 1, making A=(5,5,5).
This is the minimum number of operations required, so print 4.
Sample Input 2
3 -2 -5 -2
Sample Output 2
2
You can make A satisfy the condition with two operations as follows:
- Choose i=1, and decrease A_1 by 1 and increase A_2 by 1, making A=(-3,-4,-2).
- Choose i=2, and increase A_2 by 1 and decrease A_3 by 1, making A=(-3,-3,-3).
This is the minimum number of operations required, so print 2.
Sample Input 3
5 1 1 1 1 -7
Sample Output 3
13
By performing the operations appropriately, with 13 operations you can make A=(0,0,-1,-1,-1), which satisfies the condition in the problem statement. It is impossible to satisfy it with 12 or fewer operations, so print 13.