AtCoder Beginner Contest 212 [ D - Querying Multiset ]をPythonで解く(400点、🟫茶diff)
問題
解法
最小値を計算量低く取り出すデータ管理構造、優先度付きキュー(priority queue)を使うことがポイント。
Pythonではheapqとして提供されている。
全体に対する玉の数の上下はoffset変数を作って管理。
玉を追加する時は、offset値を引いて追加する。
優先度付きキューの特徴
- 最小値(最大値)を O(logN)O(logN)で取り出す
- 要素を O(logN)O(logN) で挿入する
ことが出来ます。 通常のリストだとそれぞれ O(N)O(N) ですので高速です。
「リストの要素の挿入」と「最小値(最大値)を取り出す」ことを繰り返すような時に使います。