問題一覧 > 通常問題

No.1604 Swap Sort:ONE

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 171
作問者 : 👑 SPD_9X2SPD_9X2 / テスター : FSMFSM penguinmanpenguinman
8 ProblemId : 6370 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-14 17:30:17

問題文

$1$ ~ $N$ の整数の順列 $P$ が与えられます。順列 $P$ の $i$ 番目の項は $P_i$ で表されます。

あなたは、以下の操作を $0$ 回以上の任意の回数繰り返すことができます。

  • $|P_i - P_j| \le 1$ を満たす整数 $i$,$j$ $\left( 1 \le i < j \le N\right)$ を選び、$P_i$ と $P_j$ の値を交換する。

$P$ を単調増加列にすることができるか判定し、可能な場合は最小の操作回数を求めてください。

ただし、$P$ が単調増加列であるとは、全ての $i \left( 1 \le i < N\right)$ に関して $P_i < P_{i+1}$ が成り立つことをいいます。

入力

$N$
$P_1\ P_2\ ...\ P_N$

  • 入力は全て整数
  • $2 \le N \le 3000$
  • $1 \le P_i \le N$
  • 全ての整数 $i \left(1 \le i \le N\right)$ は、 $P$ の中にちょうど $1$ つずつ存在する。

出力

何回操作しても単調増加列にできない場合、 $-1$ を出力してください。

そうでない場合、単調増加列にするのに必要な最小の操作回数を出力してください。

最後に改行してください。

サンプル

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

$\left(3,2,1\right)$ → $\left(2,3,1\right)$ → $\left(1,3,2\right)$ → $\left(1,2,3\right)$
とすることで、 $3$ 回を達成できます。これ以上少ない回数で単調増加列にすることはできないため、 $3$ と出力します。

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

最初から単調増加列です。

サンプル3
入力
10
1 3 7 2 10 9 8 4 5 6
出力
17

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