AtCoder Beginner Contest 217 [ E - Sorting Queries ]をPythonで解く(500点、🟩緑diff)
問題
解法
問題を読んだ段階で、ソートを行うクエリをどう扱うか(普通にソートすると計算量くってTLEっぽい)がポイントと思われる。
そこで、次のように処理する。
キュー Q1と最小値を優先的に取り出す優先度付きキューQ2を用意して、クエリを以下のように処理します。
- クエリ1 : Q1に x を push する。
- クエリ2 : Q2が空かどうかによって 2 つの操作のいずれかを行う。
- Q2が空の場合、 Q1の先頭の要素を出力して pop する。
- Q2が空でない場合、 Q2の最小の要素を出力して pop する。
- クエリ3 : Q1内の要素をすべてQ2に移す。