分数: 550 点
问题陈述
给定一个长度为的整数序列 N: A=(A_1,A_2,\ldots,A_N).
Takahashi 可以按任意顺序执行以下两个操作任意次数(可能为零)。
- 选择一个整数 i 这样 1\leq i\leq N-1,并减少 A_i by 1 并增加 A_{i+1} by 1.
- 选择一个整数 i 这样 1\leq i\leq N-1,并增加 A_i by 1 并减少 A_{i+1} by 1.
求出序列所需的最少操作数 A 满足以下条件:
- \lvert A_i-A_j\rvert\leq 1 对于任何一对 (i,j) 之间的整数 1 和 N,包括在内。
约束
- 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
你可以 A 通过如下四次操作满足条件。
- 选择 i=1,并增加 A_1 by 1 并减少 A_2 by 1, 制作 A=(3,6,6).
- 选择 i=1,并增加 A_1 by 1 并减少 A_2 by 1, 制作 A=(4,5,6).
- 选择 i=2,并增加 A_2 by 1 并减少 A_3 by 1, 制作 A=(4,6,5).
- 选择 i=1,并增加 A_1 by 1 并减少 A_2 by 1, 制作 A=(5,5,5).
这是所需的最少操作数,因此打印 4.
示例输入 2
3 -2 -5 -2
示例输出 2
2
你可以 A 通过以下两个操作满足条件:
- 选择 i=1,并减少 A_1 by 1 并增加 A_2 by 1, 制作 A=(-3,-4,-2).
- 选择 i=2,并增加 A_2 by 1 并减少 A_3 by 1, 制作 A=(-3,-3,-3).
这是所需的最少操作数,因此打印 2.
示例输入 3
5 1 1 1 1 -7
示例输出 3
13
通过适当地执行操作, 13 您可以进行的操作 A=(0,0,-1,-1,-1),满足问题陈述中的条件。 是不可能满足的 12 或更少的操作,因此打印 13.