UVA 501 - Black Box

题目链接

题意：给定一些操作，每次add进一个数，然后第i次询问的时候输出当前第i小的数字

思路：用两个优先队列搞，相当于把序列分成两个序列，每次取的答案就是后一个队列的头

代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N = 30005;

int t, m, q, vis[N], num[N];

void solve() {
    priority_queue<int> a;
    priority_queue<int, vector<int>, greater<int> > b;
    for (int i = 1; i <= m; i++) {
	a.push(num[i]);
	b.push(a.top());
	a.pop();
	while (vis[i]--) {
	    printf("%d\n", b.top());
	    a.push(b.top());
	    b.pop();
	}
    }
}

int main() {
    scanf("%d", &t);
    while (t--) {
	scanf("%d%d", &m, &q);
	for (int i = 1; i <= m; i++)
	    scanf("%d", &num[i]);
	memset(vis, 0, sizeof(vis));
	while (q--) {
	    scanf("%d", &num[0]);
	    vis[num[0]]++;
	}
	solve();
	if (t) printf("\n");
    }
    return 0;
}