分数: 300 分
问题陈述
高桥决定整理他房间里的书架。书架上有 N 书籍,以及厚度 i第本书(1 \leq i \leq N) 是 V_i。具有不同索引的两本书可能具有相同的厚度。
高桥想要重新安排所有 N 将书籍按任意顺序排成一行,每本书只使用一次。由于相邻书籍之间的厚度差异较大看起来没有吸引力,因此他想重新排列书籍,以使相邻书籍之间的厚度绝对差异之和最小化。
具体来说,让 A_k 表示厚度 k重新排列后从左边算起的第本书。在这里, (A_1, A_2, \ldots, A_N) 是一个排列 (V_1, V_2, \ldots, V_N)。求最小值:
\sum_{k=1}^{N-1} |A_k - A_{k+1}|
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq V_i \leq 10^9
- 所有输入值均为整数。
输入
N V_1 V_2 \ldots V_N
- 第一行包含一个整数 N,代表图书数量。
- 第二行包含 N 整数 V_1, V_2, \ldots, V_N 以空格分隔,代表每本书的厚度。
输出
将相邻书籍之间的厚度绝对差之和的最小值作为整数打印在一行上。
示例输入 1
4 3 1 4 2
示例输出 1
3
示例输入 2
7 10 50 30 20 40 5 25
示例输出 2
45
示例输入 3
10 1000000000 1 500000000 250000000 750000000 100 999999999 2 123456789 987654321
示例输出 3
999999999