質問する

リンク

に答える

最初は、飛行機を中心とした1番から入力したgi番までのすべての関門を探索し、飛行機を空きドアの1つに停泊しようとした.時間複雑度はO(GP)であり,100,000 x 100,000 = 10,000,000,000時間を超えると予想され,別の方法で解くことを試みた.
しかし、私は方法が思いつかなくて、私は他の人の解答を参考にしてunion-findアルゴリズムを使っていることに気づいた.(時間の複雑さが大幅に低下)(union-findアルゴリズムは知っていたのですが、なぜこの問題に使うのか分かりません.反省しなければなりません…)
注意:他人の解答
飛行機をドッキングするときは、ドッキング可能な最大数の搭乗口に常に対応しなければならない.最大ドック数を求める必要があるからです.例:
(Ex)
1号機がゲート1にドッキングした場合、2号機はいずれのハッチにもドッキングできません.最大1台しかドッキングできません.
しかし、1号機がゲート2に停泊すれば、2号機はゲート1に停泊でき、最大2機まで停泊できる.(最高価格)
問題で与えられた最初の例の入力で簡単に説明しようとします.理解していなければ、上の参考リンクに入るとわかりやすく理解できます.
(Ex)
上の図のように、Gate 3とGate 4が接続されています.これは(parents[4] = 3)ゲイト4号がドックステーションであり、他の飛行機はドックステーションに入れないと考えられることを意味する.
与えられた例の入力とは異なり、次のAirplaneの入力が4の場合、Gate 4はドッキングステーションであるため、Gate 3上にドッキングする必要がある.(最大ドッキングステーション数を取得するには、ドッキング可能な残りの最大ゲートにドッキングする必要があります.)ここでGate 3はドッキングする飛行機がないのでドッキング可能(parents[3] = 3).
つまり、parents[x] == xであれば、x番ゲートに対向することができる.ただし、x=0を除く.parents[x] != xの場合、x番ゲートウェイに接続できないため、1番~(x-1)番ゲートウェイに空きゲートウェイを見つけなければなりません.左隣のドアを確認すればいいです.parents[x] = 0であれば、飛行機はどのドアにも入ることができず、空港は閉鎖され、どの飛行機も到着できずに終了します.(これがノード0号(Gate 0号)を作成した理由です.)
この方法でドックマークを作って問題を解くといいです.

コード#コード#

import sys

# 비행기를 도킹할 때 항상 넣을 수 있는 가장 큰 수의 게이트에 도킹해야함. (최대 도킹 수를 구해야하므로)
input = sys.stdin.readline
G = int(input())
P = int(input())
docking = list(int(input()) for _ in range(P))
parents = [i for i in range(G + 1)]
ans = 0


def find(parent, x):
    if parent[x] == x:
        return x
    parent[x] = find(parent, parent[x])
    return parent[x]  # 경로압축


def union(parent, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)

    if rootA < rootB:
        parent[rootB] = rootA
    else:
        parent[rootA] = rootB


for d in docking:
    root = find(parents, d)
    # 0일 때 끝나는 이유 -> 비행기가 어느 게이트에도 도킹할 수 없으면 공항 폐쇄되고,
    # 이후 어떤 비행기도 도착할 수 없기 때문에 더이상 탐색할 필요가 X
    if root == 0:
        break

    # union(parents, d, d - 1) --> (Ex) 2-3 연결되어있고 1은 비어있음. d=3이면 1-2-3 연결되어야 하는데
    # 3의 부모인 2와 1을 연결해야하는데, 위 코드는 3과 2를 연결해서 오류발생!
    union(parents, root, root - 1)
    ans += 1

print(ans)