问题 A: [NaOI R5T1] 照相

[命题人 : 2211247]
时间限制 : 8.000 sec  内存限制 : 128 MB

提交作业-列表解决: 0提交量: 0统计

题目描述  复制

名媛聚会结束后，Misserina 建议拍一张照，于是，她们根据入场时贴的号码来决定自己的位置。
Misserina 发现一个问题，她们一共有 $n$ 人，身高差距很大，拍出来的照片很不美观。如果按照身高重新排列，她们的编号又会相当混乱-Confusion。
于是，她们重新商量，打算让一些人先不参加这次拍照，使得编号仍然是升序排序，并且相邻两人编号差不大于 $2$。
为了表明聚会的人数，她要求 $1$ 号和 $n$ 号必须参与拍照。她想知道在这个条件下，相邻两人身高差之和最小为多少。

输入

第一行：一个整数 $n$，表示人数。
接下来 $n$ 行：每行一个整数 $a_i$，表示第 $i$ 位名媛的身高。

输出

一个整数，表示满足题目要求的前提下，相邻两人身高差之和的最小值。

样例输入  复制 

8
153
1
187
167
174
197
172
376

样例输出  复制 

249

提示

对于样例，删去第 $2,4,7$ 人，剩余人身高排列为 `153 187 174 197 376`，相邻身高差之和为 $34+13+23+179=249$。
| 测试点编号 | $n \le$ | 特殊性质 |
|:-:|:-:|:-:|
| $1,2$ | $10$ | 无 |
| $3$ | $10^6$ | 有 |
| $4 \sim 10$ | $10^6$ | 无 |
特殊性质：$\forall i \in [1,n-1] \cap \mathbb{N}^+,a_i \le a_{i+1}$。
对于全部数据：满足 $1 \le n \le 10^6,0 \le a_i \le 1000$。

必须/禁用关键字

无

来源/分类

无
提交