Streamline

题目描述

我们将在数轴上用 $N$ 个棋子玩一个单人游戏。 首先，我们把每个棋子放在某个整数坐标上。 这里，多个棋子可以放在同一坐标。 我们的目标是通过重复以下移动来访问所有 $M$ 个坐标 $X_1, X_2, ..., X_M$： Move：选择一个棋子，设其坐标为 $x$。将该棋子放到坐标 $x+1$ 或 $x-1$。 注意，初始放置棋子的坐标已被视为已访问。 求达到目标所需的最少移动次数。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $X_1$ $X_2$ $...$ $X_M$

输出格式

求达到目标所需的最少移动次数。

2 5
10 12 1 2 14

5

3 7
-10 -3 0 9 -100 2 17

19

100 1
-100000

0

提示

输入中的所有值均为整数。 $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$ 均互不相同。可以按如下方式在五次移动内实现目标，并且这是所需的最少移动次数。

最初，将两个棋子分别放在坐标 $1$ 和 $10$。 将位于坐标 $1$ 的棋子移动到 $2$。 将位于坐标 $10$ 的棋子移动到 $11$。 将位于坐标 $11$ 的棋子移动到 $12$。 将位于坐标 $12$ 的棋子移动到 $13$。 将位于坐标 $13$ 的棋子移动到 $14$。

标签: AtCoder|abc117C

来源

AtCoder|abc117C