[白俊]7570番行列

🔔 質問する

今年、大韓幼稚園に入学した子供たちは、遊び場に一列に並んだ.すべての子供が入学するには指定された番号があり、服に番号札がかかっています.しかし、子供たちはまだ番号順に並ぶことができないので、先生は以下の方法で番号順に並びたいと思っています.
方法:並んでいる子供の中から1つを選んで、一番前か一番後ろに送ります.
上記の方法を用いると、子供が移動して空席が発生すると、空席の後ろの子供は一歩一歩前に空席を埋める.
例えば、5名の子供に1~5の番号を与え、以下の順序で並びます.
5 2 4 1 3
上記の方法では、以下の番号順に並ぶことができます.

1番の子供は一番前に送ります.(5 2 4 1 3 → 1 5 2 4 3)

4番の子供を最後に送ります.(1 5 2 4 3 → 1 5 2 3 4)

5番の子供を最後に送ります.(1 5 2 3 4 → 1 2 3 4 5)

上の例では、3人の子供を一番前か一番後ろに並べ、番号順に並びます.また、2人以下の子供を一番前または一番後ろに送る方法では番号順に並ぶことはできません.したがって、この場合、番号順に並ぶには、少なくとも3人の子供を移動する必要がある.
この問題は,初めて並んだ場合に,上記手法を用いて,番号順に並んだときに前後に送られる児童数の最大値を探し出すことである.

入力

入力は2行で構成されています.最初の行は、子供の数を表す整数を与えます.2列目は1列目の子供の番号を順番に与えます.指定した番号の間にスペースがあります.ただし、子供数は1以上1000000以下の整数に制限され、子供数がNであれば、子供の番号は1~Nの整数となる.

しゅつりょく

入力では、指定された子供行に番号順に並ぶために、一番前または最後に送信された子供数の最大値を出力しなければならない.

🎯 解答方法

問題を解決する方法が思いつかないので、他のブログ記事を参考にしました.😢
他の人の解答過程を参考にして、一番前または一番後ろの児童数の最大値を求めるために、いくつかの児童対号が立っていることを求め、全体の児童数から押し出した.
たとえば、入力値をchildrenに格納し、最初に0を挿入してインデックス化すると、children=[0,5,2,4,1,3]になります.次に、各番号の子供が何番目にいるかを示す位置リストを作成します.location=[0,4,2,5,3,1]このリストの意味は、「インデックスの数が何番目にあるか」です.すなわち、locationリストの1番のインデックス値は4であり、サブ数字1が4番目のインデックスにあることを示す.このlocationリストでは、各要素が隣接し、要素より小さい場合は、より小さな値が前にあるため、移動する必要はありません.これにより,リスト内を巡回し,移動を必要としない数を増やし,全児童数との差を出力することができる.

💻 python code

n = int(input())
children = list(map(int, input().split()))
children.insert(0, 0)

location = [0 for _ in range(n+1)]
for x in range(1, n+1):
    location[children[x]] = x

max_num = -1
count = 1

for i in range(1, n):
    if location[i] < location[i+1]:
        count += 1

        if count > max_num:
            max_num = max(max_num, count)

    else:
        count = 1

print(n - max_num)