問題一覧 > 通常問題

No.2289 順列ソート

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 149
作問者 : t98slidert98slider / テスター : 👑 p-adicp-adic
1 ProblemId : 9123 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-05 21:12:19

問題文

$1$ から $N$ までの相異なる $N$ 個の要素からなる順列 $ P = (P_{1}, P_{2}, P_{3}, \cdots, P_{N})$ が与えられます。
順列 $P$ に対し、以下の操作を行うことが出来ます。

  • 整数 $i$ , $j$ ($1 \leq i < j \leq N$) を選び、 $P_{i}$ と $P_{j}$ を入れ替える。
与えられた順列 $P$ を昇順に並び替えるには最低何回操作を行う必要があるかを出力してください。

入力

$N$
$P_{1}$ $P_{2}$ $P_{3}$ $\cdots$ $P_{N}$

  • $1 \leq N \leq 100$
  • $1 \leq P_{i} \leq N$
  • $1 \leq i, j \leq N$ について $i \neq j$ を満たすとき、$P_{i} \neq P_{j}$ を満たす。
  • 入力はすべて整数

出力

与えられた順列 $P$ を昇順に並び替えるための最低操作回数を1行に出力してください。最後に改行してください。

サンプル

サンプル1
入力
3
3 1 2
出力
2

$(3, 1, 2)\ \to\ (1, 3, 2)\ \to (1, 2, 3)$ などのような並び替えで2回の操作で昇順に並び替えることができます。

サンプル2
入力
6
3 1 6 5 4 2
出力
4

サンプル3
入力
1
1
出力
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。