この問題は、多重集合に対して \(1\) つの要素を追加、最小値の取得・削除を行うことにより解くことができます。

この操作は、優先度付きキューと呼ばれるデータ構造を用いて行うことができます。優先度付きキューは競技プログラミングにおいてメジャーな多くの言語に標準ライブラリとして存在しています。

また、この問題では制約が十分小さいため、愚直な方法でこの問題を解くこともできます。

例えば、\(C_i\) を現時点での袋の中に入っている \(i\) が書かれたボールの個数としてデータを持ち更新していく方法や、袋の中に入っているボールの多重集合を優先度付きキューではなく単に列として管理するような解法が考えられます。

実装例

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

int main() {
	int q;
	cin >> q;
	priority_queue<int, vector<int>, greater<>> pq;
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int x;
			cin >> x;
			pq.push(x);
		}
		else {
			int x = pq.top(); pq.pop();
			cout << x << '\n';
		}
	}
}

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

int main() {
	int q;
	cin >> q;
	vector<int> c(101);
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int x;
			cin >> x;
			c[x]++;
		}
		else {
			for (int i = 1; i <= 100; i++) {
				if (c[i] > 0) {
					c[i]--;
					cout << i << '\n';
					break;
				}
			}
		}
	}
}