問題一覧 > 通常問題

No.365 ジェンガソート

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 478
作問者 : 🍡yurahuna🍡yurahuna / テスター : btkbtk
33 ProblemId : 1081 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-04-29 23:21:39

問題文

$N$ 個のブロックが横一列に並んでいます。ブロックの長さはそれぞれ $1, 2, ..., N$ ですが、順番はバラバラです。
yurahuna君は、ブロックを左から見て長さの小さい順になるように並び替えることにしました。
ただしyurahuna君にできるのは「ブロックを1つ選び、そのブロックを一番左に移動する」という操作のみです。
(もし一番左のブロックを選んだ場合、操作後のブロックの並びは変わりませんが、これも1回の操作と数えることにします。)

さて、yurahuna君は最小何回の操作でブロックを並び替えることができるでしょうか?

入力

$N$
$a_1$ $a_2$ ... $a_N$

  • 1行目には、ブロックの個数 $N$ $(1 \leq N \leq 100000)$ が与えられる。
  • 2行目には、ブロックの長さ $a_i$ $(1 \leq i \leq N, 1 \leq a_i \leq N)$ がスペース区切りの整数で与えられる。
    $a_i$ は左から $i$ 番目のブロックの長さを表す。
    • ブロックの長さはすべて異なる。すなわち、すべての $i, j$ $(1 \leq i < j \leq N)$ について、$a_i \neq a_j$ である。

出力

yurahuna君がブロックを並び替えるのにかかる最小の操作回数を1行で出力してください。
最後に改行してください。

サンプル

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

まず長さ2のブロックを選んで一番左に移動し、次に長さ1のブロックを選んで一番左に移動すると、左から見て長さの小さい順になります。これは操作回数が最小となる並び替え方です。
3 1 4 2 5

2 3 1 4 5

1 2 3 4 5

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

長さ3, 2, 1の順にブロックを選んで操作すると最小回数で並び替えられます。

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

既に左から見て長さの小さい順になっているので、yurahuna君は1回も操作を行わなくてよいです。

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