https://atcoder.jp/contests/abc117/tasks/abc117_c
数直線上に地点X_iを配置して、コマが移動した位置を塗りつぶすことを考える。
移動回数を最小化したいので、塗りつぶす面積を最小化することを考える。
X_1, …, X_M によって M-1 個の区間が作られる。
N=1だったら全ての区間をぬりぶさないとM個の地点全てに到達できない。 N=2だったら一つの区間は塗りつぶさずにスキップできる。 このように考えると、最大N-1個の区間は塗りつぶさずにスキップ可能であることがわかる。 よって、塗りつぶさないといけない区間はmax(0, M-N)個。
区間の長さをソートし、短い順にmax(0, M-N)個の区間の長さの合計を求めると答えになる。