Score : 300 points
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.
Input is given from Standard Input in the following format:
N M X_1 X_2 ... X_M
Find the minimum number of moves required to achieve the objective.
2 5 10 12 1 2 14
5
The objective can be achieved in five moves as follows, and this is the minimum number of moves required.
3 7 -10 -3 0 9 -100 2 17
19
100 1 -100000
0