AOJ Sort II - Minimum Cost Sort

学校の別のコースの人の授業でやった問題らしいので軽い気持ちでやってみたけど, 全然わからなかった…

問題

最小コストソート | アルゴリズムとデータ構造 | Aizu Online Judge

解法

まず基本的な考察をします。例えば 10 7 8 9 といった数列を考えると, 最終的には 7 8 9 10 となるはずです。

ということは, 10 は今 9 がある位置に移動して, 9 は今 8 がある位置に移動して, 8 は今 7 がある位置に移動して, 7 は今 10 がある位置に移動します。これを 10 -> 9 -> 8 -> 7 -> 10 というように表すと, 巡回群っぽいです。

この数列を 7 8 9 10 にしたいと思ったら, 巡回群の数 n に対して n-1 回は置換をやらないともとの数列に戻りません。じゃあ n-1 回をどのように置換するのが最適かというと, 常に巡回群の最小の数を起点にするように動かすのが最適です。

今回の場合は, (7, 8) -> (7, 9) -> (7, 10) と置換していくのが明らかにコスト最小です。この時のコストは 48 ですね。

例に出した数列ではこれで良いのですが, この考え方には反例があります。
数列 1 10 7 8 9 を考えます。先ほどの例の数列の一番前に 1 を追加しただけの数列です。この数列は, 巡回群 [1] と [10 -> 9 -> 8-> 7 -> 10] で構成されており, 上と同じようにコストを計算すると,
[1] に対するコストは 0, [10 -> 9 -> 8-> 7 -> 10] に対するコストは 48 で, 合計コストは 48 です。

しかし, 先に 1 と 7 を交換してから 巡回群を [10 -> 9 -> 8 -> "1" -> 10] とみなして置換していき, 最後に 1 と 7 を再び交換すると考えるとどうでしょうか。

この場合は, かかるコストは 2*(1+7) + 1*3 + 8+9+10 = 46 で, 先程よりもお得です。

このようなことがあるので, 巡回群を戻す際の選択肢は,
・巡回群を構成する最小値のスワップで元に戻す
・巡回群の外にある最小値を使ってスワップする
という 2 通りの可能性があります。

これら 2 通りの可能性を 各巡回群に対して調べて最小コストを求めれば答えを得ることが出来ます。

const int MAXN = 1010;
int w[MAXN];
bool done[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, mini = 100000;
    cin >> n;
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
        mp[w[i]] = 0;
        mini = min(mini, w[i]);
    }
    {
        int k = 0;
        for (auto& p : mp) p.second = k++;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (done[i]) continue;
        int cnt = 0, now = i, mi = 100000, sum = 0;
        while (1) {
            if (done[now]) break;
            cnt++;
            done[now] = true;
            mi = min(mi, w[now]);
            sum += w[now];
            now = mp[w[now]];
        }
        int tmp = sum+(cnt-2)*mi;
        tmp = min(tmp, sum+mi+mini*(cnt+1));
        ans += tmp;
    }
    cout << ans << endl;
    return 0;
}