ソートする問題。

問題概要

$N$ 個のコマを数直線上に配置して、それぞれ移動させる。

それによって、 $M$ 個の地点 $X_1, X_2, \dots, X_M$ をすべて訪れるようにしたい。総移動距離の最小値を求めよ。

制約

$1 \le N, M \le 10^{5}$

考えたこと

とりあえず、各コマについて、「行って、引き返して」とやることは完全に無駄であることから、各コマは一度動いたらその方向にしか動かないものと思うことができる (こんな感じの「〜するのは無駄だから考えなくて良い」という考察は典型だと思われる)。

さらに、進む方向は X 軸方向の正の向きとして差し支えない。そう考えると、各コマは

数直線上の区間 (長さが 0 であってもよい)

と同一視してよいことがわかる。つまり $N$ 個の区間によって、 $M$ 個の座標を完全に被覆する問題だということになる。

ここで、これらの区間の両端点は、 $M$ 個の座標として指定されているチェックポイント部分 (下図の黒丸部分) のみに限定してよいことがわかる (はみ出しても意味がないため)。

さらにこれは補集合をとると、

$N-1$ 箇所の覆われていない「隣り合う 2 点」

に対応していることがわかる。これを最大にすればいいことがわかる。よって問題は

「隣り合う 2 点」の距離を表す $M-1$ 個の数値を大きい順にソートして
大きい順に $N-1$ 個を足す ( $M-1$ 個に達したら終了)

とすればいいことがわかる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, M; cin >> N >> M;
    vector<long long> X(M);
    for (int i = 0; i < M; ++i) cin >> X[i];
    sort(X.begin(), X.end());
        
    vector<long long> diffs;
    for (int i = 1; i < X.size(); ++i) diffs.push_back(X[i] - X[i-1]);
    sort(diffs.begin(), diffs.end(), greater<long long>());
        
    long long res = X.back() - X[0];
    for (int i = 0; i < min((int)diffs.size(), N-1); ++i) res -= diffs[i];
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 117 C - Streamline (4Q, 茶色, 300 点)

問題概要

制約

考えたこと