Score : $550$ points

问题描述

给定一个长度为 $N$ 的整数序列：$A=(A_1,A_2,\ldots,A_N)$。

高桥可以按照任意顺序执行以下两种操作任意次，包括零次。

• 选择一个整数 $i$，满足 $1\leq i\leq N-1$，将 $A_i$ 减 $1$ 并将 $A_{i+1}$ 加 $1$。
• 选择一个整数 $i$，满足 $1\leq i\leq N-1$，将 $A_i$ 加 $1$ 并将 $A_{i+1}$ 减 $1$。

求解使得序列 $A$ 满足以下条件所需的最小操作次数：

• 对于任何一对在 $1$ 和 $N$ 之间的整数 $(i,j)$，有 $\lvert A_i-A_j\rvert\leq 1$。

以上为通义千问 qwen-max 翻译，仅供参考。

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$.

update @ 2024/3/10 08:42:35