201204: [AtCoder]ARC120 E - 1D Party

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

Description

Score : $700$ points

Problem Statement

There are $N$ people, Person $1$ through Person $N$, standing on a number line. Person $i$ is now at coordinate $A_i$ on the number line.
Here, $A_1 < A_2 < A_3 < \dots < A_N$ and all $A_i$ are even numbers.

We will now hold a party for $k$ seconds.
During the party, each person can freely move on the number line at a speed of at most $1$ per second. (It is also allowed to move in the negative direction within the speed limit.)
The people request that the following condition be satisfied for every integer $i$ such that $1 \le i \lt N$:

  • there is at least one moment during the party (including the moment it ends) when Person $i$ and Person $i + 1$ are at the same coordinate.

Find the minimum $k$ for which there is a strategy that the people can take to satisfy all the conditions.
We can prove that the answer is an integer under the Constraints of this problem.

Constraints

  • $2 \le N \le 2 \times 10^5$
  • $0 \le A_i \le 10^9$
  • $A_1 < A_2 < A_3 < \dots < A_N$
  • $A_i$ is an even number.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$

Output

Print the answer as an integer.

Sample Input 1

3
0 6 10

Sample Output 1

5

During the party lasting $5$ seconds, each person should move as follows:

  • Person $1$: always moves in the positive direction at a speed of $1$.
  • Person $2$: moves in the positive direction at a speed of $1$ during the first $2$ seconds, then in the negative direction at a speed of $1$ during the remaining $3$ seconds.
  • Person $3$: always moves in the negative direction at a speed of $1$.

If they move in this way, Person $2$ and Person $3$ will be at the same coordinate exactly $2$ seconds after the beginning, and Person $1$ and Person $2$ will be at the same coordinate at the end of the party.
Thus, they can satisfy all the conditions for $k = 5$. For smaller $k$, there is no strategy to satisfy all of them.

Sample Input 2

5
0 2 4 6 8

Sample Output 2

3

During the party lasting $3$ seconds, each person should, for example, move as follows:

  • Person $1$: always moves in the positive direction at a speed of $1$.
  • Person $2$: moves in the positive direction at a speed of $1$ during the first $2$ seconds, then in the negative direction at a speed of $1$ during the remaining $1$ second.
  • Person $3$: does not move at all.
  • Person $4$: moves in the negative direction at a speed of $1$ during the first $2$ seconds, then in the positive direction at a speed of $1$ during the remaining $1$ second.
  • Person $5$: always moves in the negative direction at a speed of $1$.

Sample Input 3

10
0 2 4 6 8 92 94 96 98 100

Sample Output 3

44

Input

题意翻译

# 题目描述 有 $ N $ 个人打算开派对，他们均分布在数轴上，编号从1到$N$,第i个人位于 $ a_i $点。初始是他们都位于数轴上不同的点。具体的，所有人所在的点都属偶数点，且有 $ a_1 < a_2 < a_3$ ... $< a_n$ 派对计划进行 k 秒，每个人每秒钟可以在数轴上向左或者向右移动一个单位长度，也可以不移动。 我们都知道，开派对至少要两个人。所以派对成功举行的条件是，对于任意的某个人 $j (1≤j<N)$，经过一系列移动过程，在派对进行中至少有一瞬间（包括派对结束的那一刻）使得 $a_j = a_{j+1}$（以当前那一秒结束时的位置为准）。 请计算能够使得派对成功举行的最小的 $k$。 能够证明在题目限定条件下答案一定存在。 # 输入格式 共 $2$行： 第一行，一个正整数 $N$ 第二行，包含 $ N $ 个正整数 $a_i$ # 输出格式 一行，一个整数，表示满足条件的最小$k$值 # 样例解释 ## 样例1解释 我们依次把 3 个人记为 $A,B,C$,在 5 秒内，每个人可以进行如下方式的移动： $A$ 一直向右移动； $B$ 前2秒向右移动，后3秒向左移动； $C$ 一直向左移动。 这样 $B$ 和 $C$ 在第 2 秒结束时到达同一个位置，$A$ 和 $B$ 在第 5 秒结束时到达同一个位置。 ## 样例2解释 我们依次把 5 个人记为 $A,B,C,D,E$ $A$ 一直向右移动； $B$ 前 2 秒向右移动，后 1 秒向左移动； $C$ 一直保持不动； $D$ 前 2 秒向左移动，后 1 秒向右移动； $E$ 一直向左移动； 这样 $(B,C),(C,D)$ 同时在第 2 秒结束时到达同一个位置，$(A,B),(D,E)$ 分别在第 3 秒结束时到达同一个位置。

Source/Category

加入题单

上一题 下一题 算法标签：