ALDS1_6_D: Minimum Cost Sort

ちょっと時間がない

普通にソートしてみてからその結果に持っていけるように交換順序を考える

と

重いものから順に正しい位置へ

で１次近似しよう

サンプルデータふたつはこれでも正しい値が出るはず
データがよくない気もするけど

ソートとサーチは素直にライブラリ関数を使った
O(n²)

def swap(w, i, j):
    tmp = w[i]
    w[i] = w[j]
    w[j] = tmp

def min_weight(w):
    ws = sorted(w)
    weight = 0
    for i in reversed(range(len(w))):
        j = w.index(ws[i])
        if i != j:
            weight += w[i] + w[j]
            swap(w, i, j)
    return weight

def main():
    n = int(input())
    w = [int(x) for x in input().split()]
    print(min_weight(w))

main()

はい3つめのデータでWA
テストデータだとこれが48

4
10 7 8 9

上のプログラムだと51
10↔9、9↔8、8↔7という手順

48はどういう手順かな
7↔8、7↔9、7↔10でいいのか
うーん大きな数から正しい位置に、という戦略がそもそもダメってことか