← 返回题目列表

AtCoder · abc307_g

G. 近似均衡

中文机器翻译题面 查看原题

分数: 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.