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