#P13691. [ARC120E] 1D Party

    ID: 12893 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-线性 DP有限候选集缩减区间求交三角不等式添加哨兵

[ARC120E] 1D Party

题目描述

有 N N 个人打算开派对,他们均分布在数轴上,编号从 11 到 NN,第 ii 个人位于 ai a_i 点。初始是他们都位于数轴上不同的点。具体的,所有人所在的点都是偶数点,且有 a1<a2<a3<⋯<an a_1 < a_2 < a_3 <\cdots< a_n。

派对持续 kk 秒。每个人可以沿数轴向任意方向移动或停下,移动速度不超过每秒 11 个单位。

对于每个 1≤j<N1\le j<N,编号为 jj 和 j+1j+1 的两个人须在派对期间的某一时刻处于同一位置。允许在派对结束时相遇。

请计算能够使得派对成功举行的最小的 kk。

能够证明在题目限定条件下答案一定存在。

输入格式

第一行一个正整数 NN。
第二行给出 NN 个整数 a1,…,aNa_1,\ldots,a_N。

输出格式

一行一个整数,表示满足条件的最小 kk 值。

样例解释

样例 1 解释

我们依次把 33 个人记为 A,B,CA,B,C,在 55 秒内,每个人可以进行如下方式的移动:

  • AA 一直向右移动;
  • BB 前 22 秒向右移动,后 33 秒向左移动;
  • CC 一直向左移动。

这样 BB 和 CC 在第 22 秒结束时到达同一个位置,AA 和 BB 在第 55 秒结束时到达同一个位置。

样例 2 解释

我们依次把 55 个人记为 A,B,C,D,EA,B,C,D,E。

  • AA 一直向右移动;
  • BB 前 22 秒向右移动,后 11 秒向左移动;
  • CC 一直保持不动;
  • DD 前 22 秒向左移动,后 11 秒向右移动;
  • EE 一直向左移动;

这样 (B,C),(C,D)(B,C),(C,D) 同时在第 22 秒结束时到达同一个位置,(A,B),(D,E)(A,B),(D,E) 分别在第 33 秒结束时到达同一个位置。

输入输出样例 #1

输入 #1

3
0 6 10

输出 #1

5

输入输出样例 #2

输入 #2

5
0 2 4 6 8

输出 #2

3

输入输出样例 #3

输入 #3

10
0 2 4 6 8 92 94 96 98 100

输出 #3

44

数据范围

2≤N≤2×1052\le N\le 2\times10^5,0≤a1<a2<⋯<aN≤1090\le a_1<a_2<\cdots<a_N\le10^9,且每个 aia_i 都是偶数。答案为整数。

AtCoder 原题