東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 307）
翻译中…
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.
翻译中…
样例
Input #1
3
2 7 6
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$.
Input #2
3
-2 -5 -2
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$.
Input #3
5
1 1 1 1 -7
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$.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。