コンテンツにスキップ

集合

タグ「集合」の記事 1 件

DOJ Beginner Contest 8 B - Subway Seats

地下鉄の車両に NN 個の座席があり、最初はすべて空いています。MM 人の乗客が順に乗ってきて、ii 人目は座席 AiA_i に座ろうとします。空いていれば座り、すでに誰かが座っていれば立ったままになります。最後に立っている人数を求める問題です。

座れるのは、各座席について最初にその座席を希望した人だけです。座れる人数は AA に現れる値の種類数に等しいので、答えは M−(A の値の種類数)M - (A \text{ の値の種類数}) です。

種類数は、set に入れて大きさを見れば求まります。

Python
for _ in range(int(input())):
N, M = map(int, input().split())
A = list(map(int, input().split()))
print(M - len(set(A)))