103076: [Atcoder]ABC307 G - Approximate Equalization

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $550$ points

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

Input

题意翻译

给定一个长度为 $n$ 的序列 $a$，你可以： + 选择 $1\leq i<n$，令 $a_i$ 减去 $1$、$a_{i+1}$ 加上 $1$。 + 选择 $1\leq i<n$，令 $a_i$ 加上 $1$、$a_{i+1}$ 减去 $1$。 你要让 $a$ 中任意两个数相差不超过 $1$，输出最少步数。

Output

得分：550分 部分 问题描述 给定一个长度为 N 的整数序列 A：A = (A1, A2, ..., AN)。 Takahashi 可以在任何顺序执行任意次数（包括零次）以下两种操作之一。 选择一个整数 i，满足 1≤i≤N−1，并将 A[i] 减少 1，并将 A[i+1] 增加 1。 选择一个整数 i，满足 1≤i≤N−1，并将 A[i] 增加 1，并将 A[i+1] 减少 1。 找出使序列 A 满足以下条件所需的最少操作次数： 对于任何整数对 (i, j) 在 1 和 N 之间（包括），都有 |Ai−Aj|≤1。 部分 约束 2≤N≤5000 |Ai|≤109 所有输入值都是整数。 部分 输入 输入以以下格式从标准输入给出： N A1 A2 ... AN 部分 输出 打印一行，包含使序列 A 满足问题描述中的条件所需的最少操作次数。 部分 样例输入 1 3 2 7 6 部分 样例输出 1 4 你可以通过以下四种操作使 A 满足条件： 选择 i=1，将 A1 增加 1，并将 A2 减少 1，使 A=(3,6,6)。 选择 i=1，将 A1 增加 1，并将 A2 减少 1，使 A=(4,5,6)。 选择 i=2，将 A2 增加 1，并将 A3 减少 1，使 A=(4,6,5)。 选择 i=1，将 A1 增加 1，并将 A2 减少 1，使 A=(5,5,5)。 这是所需的最少操作次数，因此打印 4。 部分 样例输入 2 3 -2 -5 -2 部分 样例输出 2 2 你可以通过以下两种操作使 A 满足条件： 选择 i=1，将 A1 减少 1，并将 A2 增加 1，使 A=(-3,-4,-2)。 选择 i=2，将 A2 增加 1，并将 A3 减少 1，使 A=(-3,-3,-3)。 这是所需的最少操作次数，因此打印 2。 部分 样例输入 3 5 1 1 1 1 -7 部分 样例输出 3 13 通过适当执行操作，你可以用 13 次操作使 A=(0,0,-1,-1,-1)，满足问题描述中的条件。 用 12 次或更少的操作无法满足条件，因此打印 13。

Source/Category

加入题单

上一题 下一题 算法标签：