Approximate Equalization

题目描述

给定长度为 $N$ 的整数序列：$A=(A_1,A_2,\ldots,A_N)$。 Takahashi 可以任意次（可能为零次、按任意顺序）执行以下两个操作。

选择一个整数 $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$ 满足以下条件所需的最小操作次数：

$\lvert A_i-A_j\rvert\leq 1$ 对于任意在 $1$ 到 $N$（含）之间的整数对 $(i,j)$ 成立。

输入格式

输入由标准输入给出，格式如下： $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

打印一行，包含使序列 $A$ 满足题目中条件所需的最小操作次数。

3
2 7 6

4

3
-2 -5 -2

2

5
1 1 1 1 -7

13

提示

$2 \leq N \leq 5000$ $\lvert A_i \rvert \leq 10^9$ 所有输入值均为整数。你可以通过如下四次操作使 $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$。
你可以通过如下两次操作使 $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$。
通过适当执行操作，使用 $13$ 次操作你可以使 $A=(0,0,-1,-1,-1)$，它满足题目中的条件。 无法在 $12$ 次或更少操作下使其满足，因此输出 $13$。

标签: AtCoder|abc307G

来源

AtCoder|abc307G