1674 Sorting by Swapping

概要

n <=10000 この数からなる数列が与えられる．
この数列は，1〜nの順列になっている．
この数列を，任意の場所との交換だけでソートする．
最低何回交換操作をしないといけないか．

解法

順列になっているので，ある数字がどこにあるか，と言うのがすぐに分かる．
そのため，1番目から順番に正しい数字かチェックし，違うならば正しい数字と交換する，と言う操作が，定数時間でできるため，O(n)で交換回数を数えられる．