yukicoder #482: あなたの名は

解法

N>=2なので

ソートするのにかかる最小の交換回数をsとしたとき

s-K>=0 かつ 2 | (s-K) ならばOK

与えられているのは順列で、グラフにしてみるとsの求め方はわかりやすい。複数のサイクルに分割できてサイクルごとにソートするのが最も交換回数が少なくて済む。

f:id:parukii:20170213131923j:plain

広告を非表示にする