AT_abc307_g [ABC307G] Approximate Equalization

题目描述

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

高桥君可以无限次（也可以不进行）重复以下两种操作中的任意一种：

• 选择满足 $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\leq i,j\leq N$，都有 $|A_i-A_j|\leq 1$。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出使数列 $A$ 满足题目条件所需的最小操作次数。

输入输出样例 #1

输入 #1

3
2 7 6

输出 #1

4

输入输出样例 #2

输入 #2

3
-2 -5 -2

输出 #2

2

输入输出样例 #3

输入 #3

5
1 1 1 1 -7

输出 #3

13

说明/提示

限制条件

• $2\leq N\leq 5000$
• $|A_i|\leq 10^9$
• 输入均为整数

样例解释 1

可以通过如下方式在 $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

可以通过如下方式在 $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

通过合理操作，在 $13$ 次操作后可以得到 $A=(0,0,-1,-1,-1)$，满足题目条件。用 $12$ 次或更少的操作无法满足条件，因此输出 $13$。

由 ChatGPT 4.1 翻译