POJ1442 (Black Box)做题笔记

发表于 | 更新于 | | 阅读次数：

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://poj.org/problem?id=1442

这题题意是给定两个序列，第一个序列是输入序列，第二个序列是询问序列，第二个序列的第i个数bi是询问输入第bi个数时黑盒的第i小

乍一看每次询问第i小好像需要用平衡树，但其实这题可以用priority_queue直接水过去，创建两个priority_queue，小根堆中存的数大于大根堆中存的数。严格保持大根堆有i个数，这样小根堆中的根就是整个黑盒的第i+1大了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
const int M=30009;
int a[M];
int pos=0;
std::priority_queue<int, std::vector<int>, std::greater<int> > big;
std::priority_queue<int, std::vector<int>, std::less<int> > small;
int main() {
	int m,n;
	int t;
	int tmp;
	scanf("%d%d",&m,&n);
	for (int i=0;i<m;i++) scanf("%d",&a[i]);
	for (int i=0;i<n;i++) {
		scanf("%d",&t);
		for (;pos<t;pos++) {
			if (!small.empty()&&small.top()>a[pos]) {
				small.push(a[pos]);
				tmp=small.top();
				small.pop();
				big.push(tmp);
			}
			else big.push(a[pos]);//,printf("%d %d*\n",a[pos]);
		}
		tmp=big.top();
		printf("%d\n",tmp);
		small.push(tmp);
		big.pop();
	}
	return 0;
}