← 返回题目列表

AtCoder · awc0020_c

C. 整理书架

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

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