← 返回题目列表

AtCoder · arc120_e

E. 一维派对

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

分数: 700 点

问题陈述

有 N 人、人 1 通过人 N,站在数轴上。人 i 现在位于坐标处 数轴上的 A_i 。
在这里, A_1 < A_2 < A_3 < \dots < A_N 和所有 A_i 是偶数。

我们现在将为 k 秒。
聚会期间,每个人可以在数轴上自由移动,速度最多为 1 每秒。 (也允许在限制速度内向负方向移动。)
人们要求每个整数都满足以下条件 i 这样 1 \le i \lt N:

  • 在聚会期间(包括结束的那一刻)至少有一个时刻,人 i 和人 i + 1 位于同一坐标。

求最小值 k 对此,人们可以采取一种策略来满足所有条件。
我们可以证明在这个问题的约束下答案是一个整数。

约束

  • 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 是偶数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 A_3 \dots A_N

输出

将答案打印为整数。


示例输入 1

3
0 6 10

示例输出 1

5

聚会持续期间 5 秒,每个人应按如下方式移动:

  • 人 1:始终以速度正方向移动 1.
  • 人 2:以速度正方向移动 1 在第一次期间 2 秒,然后以速度负方向 1 在剩余时间内 3 秒。
  • 人 3:始终以速度向负方向移动 1.

如果他们以这种方式移动,人 2 和人 3 将完全位于同一坐标 2 开始后几秒,以及 Person 1 和人 2 将在聚会结束时位于同一坐标。
因此,他们可以满足所有条件 k = 5。对于较小的 k,没有任何策略可以满足所有这些。


示例输入 2

5
0 2 4 6 8

示例输出 2

3

聚会持续期间 3 秒,每个人应该例如如下移动:

  • 人 1:始终以速度正方向移动 1.
  • 人 2:以速度正方向移动 1 在第一次期间 2 秒,然后以速度负方向 1 在剩余时间内 1 第二。
  • 人 3:根本不动。
  • 人 4:以速度向负方向移动 1 在第一次期间 2 秒,然后以速度正方向 1 在剩余时间内 1 第二。
  • 人 5:始终以速度向负方向移动 1.

示例输入 3

10
0 2 4 6 8 92 94 96 98 100

示例输出 3

44