分数: 300 点
问题陈述
我们将使用数轴玩一个单人游戏, N 件。
首先,我们将每个片段放置在某个整数坐标处。
这里,多个棋子可以放置在同一坐标处。
我们的目标是访问所有 M 坐标 X_1, X_2, ..., X_M 使用这些棋子,重复以下动作:
移动: 选择一块并让 x 是它的坐标。把那块放在坐标上 x+1 or x-1.
请注意,我们最初放置棋子的坐标已经被视为已访问。
找出实现目标所需的最少移动次数。
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- -10^5 \leq X_i \leq 10^5
- X_1, X_2, ..., X_M 都是不同的。
输入
输入由标准输入按以下格式给出:
N M X_1 X_2 ... X_M
输出
找出实现目标所需的最少移动次数。
示例输入 1
2 5 10 12 1 2 14
示例输出 1
5
可以通过如下五步来实现目标,这是所需的最少步数。
- 最初,将两块放在坐标处 1 和 10.
- 将工件移动到坐标处 1 to 2.
- 将工件移动到坐标处 10 to 11.
- 将工件移动到坐标处 11 to 12.
- 将工件移动到坐标处 12 to 13.
- 将工件移动到坐标处 13 to 14.
示例输入 2
3 7 -10 -3 0 9 -100 2 17
示例输出 2
19
示例输入 3
100 1 -100000
示例输出 3
0