ALDS1_6_D: Minimum Cost Sort (続き2)

荷物を重さの順にソートするんだけど、要素の交換のときに重さに応じた コストがかかり、トータルのコストが最小になるようにソートするというもの

ALDS1_6_D: Minimum Cost Sort - kb84tkhrのブログ

あきらめて解説を読む

各要素が最終的にどの位置へ移動するかを矢印で表すと
要素がいくつかのグループに分かれてサイクルができる
サイクルごとに最小コストを考えると、いちばん小さい要素を使って
入れ替えていくのが一番コストが低い

まあそこまではいい

このアルゴリズムには反例があります。

そこですよ
2 1 8 10 7 9に上のアルゴリズムを適用するとこうなって

コストが51
7,8,9,10で回すのはすごい高コストで
7と1を入れ替えてから回し、もう一度7と1を入れ替えるとこうなって

こっちの方がコストが低くなる
こういう可能性は気づいてた

各サイクルのコストは要素全体の最小値をかりた場合とかりない場合を計算し、コストが小さいほうを採用する必要があります。

その方がいいのはわかる
けどそれで最小が保証されたのかどうかやっぱりよくわからないんだよな
このアルゴリズムには反例がないと言い切れるの

コードは一目瞭然というほどではないけど落ち着いて読めばわかる

def solve(n, A):
    VMAX = 10000

    ans = 0
    s = min(A)
    V = [False] * n
    B = sorted(A)
    T = {B[i]: i for i in range(n)}

    for i in range(n):
        if V[i]:
            continue
        cur = i
        S = 0
        m = VMAX
        an = 0
        while not V[cur]:
            V[cur] = True
            an += 1
            v = A[cur]
            m = min(m, v)
            S += v
            cur = T[v]
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)
    return ans

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    print(solve(n, A))

main()

変数がいっぱいあるから追っかけにくいんだな
といっても単純にmapとかreduceになる形でもなさそう