← 返回题目列表

AtCoder · abc117_c

C. 精简

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

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