[問題解決]白準-1075空港(互いに集合)

提问链接

問題の説明

今日はシン・スンウォンの誕生日です.
朴スンウォンは誕生日にシン・スンウォン仁川国際空港にプレゼントした.
空港にはGドアがあり、それぞれ1~Gの番号があります.
空港はP機に順番に到着し、gi(1≦gi≦g)の最初の関門の一つに永久的に接続しようとします.飛行機がいずれの搭乗口にも停泊できないと、空港は閉鎖され、その後はどの飛行機も到着できません.
シン・スンウォンは一番多い飛行機を空港に止めて、朴スンウォンを幸せにしたいと思っている.勝元は最大何機の飛行機をドッキングさせることができますか?

入力

第1行は格子の個数G(1≦G≦105)を与える.
2行目は飛行機数P(1≦P≦105)を与える.
その後、P行にgi(1≦gi≦G)を付与する.

しゅつりょく

乗員がドッキングできる最大飛行機数を出力します.

入力例1

4
3
4
1
1

サンプル出力1

2

私の答え

答えを出す。

서로소 집합で解決しました.
各ゲートを異なる集合として表し、飛行機が入ると順次ゲートを受け取る必要があるが、できるだけ大きな番号のゲートを受け取るようにしなければならない.
ドッキングプロセスがマージされます.
Unionプロシージャ(ドッキングされている場合)は、左側のコレクションとマージされます.
コレクションのルートが0の場合、ドッキングはできないと考えられます.

説明する。

白峻で見つけたクイック解答.

コード#コード#

セット使用

import sys
input = sys.stdin.readline
def find(parent, x):
    if parent[x] != x:
        parent[x]= find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a<b:
        parent[b] = a
    else:
        parent[a] = b

gate = int(input())
plane = int(input())
parent = [0]*(gate+1)
for i in range(1, gate+1):
    parent[i] = i

result = 0
for _ in range(gate):
    d = find(parent, int(input()))
    if d == 0:
        break
    union(parent, d, d-1) # 왼쪽 집합과 합집합
    result += 1
print(result)

その他のプール

import sys 
input = sys.stdin.readline
gate = int(input())
plane = int(input())
gates = [0]*(gate+1)
for i in range(plane):
    p = int(input())
    while True:
        gates[p] += 1
        if gates[p] == 1:
            break
        if gates[p] > p:
            print(i)
            sys.exit(0)
        p -= gates[p]
        p+= 1
print(plane)