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
になる形でもなさそう