Streamline [AtCoder Beginner Contest 117 C]

https://atcoder.jp/contests/abc117/tasks/abc117_c

解説

https://atcoder.jp/contests/abc117/submissions/4162169

隣接する点に移動するというのと、ソートできるときは大体したほうがいいので、Xをソートする。
まずは最適行動について考えてみよう。
すると、あるコマが担当する地点は区間の形になる。
飛び飛びになることは無い。
ある区間が1つのコマの担当であるとわかった場合は、端を初期位置として、もう一方の端に向かわせればいい。
　
ここから、グラフ問題のある問題へ帰着させる。
地点を頂点、ソート後に隣接する地点の差を見て、これを辺と考える。
最初はM個の連結成分となっているが、ここからいくつかの辺を使って連結成分をN個にする。
辺を1つ採用することで連結成分が1つ減るので、移動回数を最小化するには辺のコストが小さい方からM-N個取ればいい。
　
総括すると、Xをソートして、隣接する地点の差を取った配列dを用意する。
この配列の小さい方からM-N個取ってきた総和が答え。
M-N＜0の場合はM＜Nなので、持っているコマを全ての地点におけるので、0が答え。

int N, M, X[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> X[i];
    sort(X, X + M);
 
    vector<int> d;
    rep(i, 0, M - 1) d.push_back(X[i + 1] - X[i]);
    sort(all(d));
 
    ll ans = 0;
    int cnt = max(0, M - N);
    rep(i, 0, cnt) ans += d[i];
    cout << ans << endl;
}