鉄則本 A53 - Priority Queue (4Q, ★2)

優先度付きキューを人生で初めて試すのにいい問題。　

• 問題へのリンク

問題概要

以下の 3 種類のクエリ ( 個) を高速に処理するプログラムを実装せよ。販売システムを模している。

• クエリタイプ 1：価格が 円の商品が追加される
• クエリタイプ 2：今ある商品の中の最小価格を答える
• クエリタイプ 3：最も安い商品が 1 つ売れる

初期状態では、商品が 1 つもない。また、クエリタイプ 2, 3 が呼ばれるときには、商品が 1 つ以上あることが保証される。

制約

• 

メモ

C++ であれば priority_queue が使える。詳しい解法は鉄則本参照。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int Q, type, price;

    cin >> Q;
    priority_queue<int, vector<int>, greater<int>> que;  // キュー
    while (Q--) {
        cin >> type;
        if (type == 1) {
            cin >> price;
            que.push(price);
        } else if (type == 2) {
            cout << que.top() << endl;
        } else {
            que.pop();
        }
    }
}