/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
数直線と N 個のコマを用いて 1 人でゲームを行います。
はじめ、これらのコマをそれぞれ好きな整数座標に置きます。
このとき、同じ座標に複数のコマを置いても構いません。
以下の移動を繰り返して、座標 X_1, X_2, ..., X_M の M 個の地点全てをいずれかのコマで訪れることが目的です。
移動: コマを 1 つ選び、そのコマの座標を x とする。そのコマを座標 x+1 もしくは座標 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
以下の手順で 5 回移動を行うと目的を達成でき、このときが最小です。
- はじめに 2 個のコマをそれぞれ座標 1, 座標 10 に置きます。
- 座標 1 のコマを座標 2 に移動します。
- 座標 10 のコマを座標 11 に移動します。
- 座標 11 のコマを座標 12 に移動します。
- 座標 12 のコマを座標 13 に移動します。
- 座標 13 のコマを座標 14 に移動します。
入力例 2
3 7 -10 -3 0 9 -100 2 17
出力例 2
19
入力例 3
100 1 -100000
出力例 3
0
Score : 300 points
Problem Statement
We will play a one-player game using a number line and N pieces.
First, we place each of these pieces at some integer coordinate.
Here, multiple pieces can be placed at the same coordinate.
Our objective is to visit all of the M coordinates X_1, X_2, ..., X_M with these pieces, by repeating the following move:
Move: Choose a piece and let x be its coordinate. Put that piece at coordinate x+1 or x-1.
Note that the coordinates where we initially place the pieces are already regarded as visited.
Find the minimum number of moves required to achieve the objective.
Constraints
- All values in input are integers.
- 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 are all different.
Input
Input is given from Standard Input in the following format:
N M X_1 X_2 ... X_M
Output
Find the minimum number of moves required to achieve the objective.
Sample Input 1
2 5 10 12 1 2 14
Sample Output 1
5
The objective can be achieved in five moves as follows, and this is the minimum number of moves required.
- Initially, put the two pieces at coordinates 1 and 10.
- Move the piece at coordinate 1 to 2.
- Move the piece at coordinate 10 to 11.
- Move the piece at coordinate 11 to 12.
- Move the piece at coordinate 12 to 13.
- Move the piece at coordinate 13 to 14.
Sample Input 2
3 7 -10 -3 0 9 -100 2 17
Sample Output 2
19
Sample Input 3
100 1 -100000
Sample Output 3
0