对顶堆的模板题
对顶堆为一个大根堆A ,和一个小根堆B ,分别维护一个序列的前一段和后一段
要求中位数，只需要将序列均分入两个堆中即可
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
34
35
36
37
38
39
40
41
42
43
44
|
#include<queue>
using namespace std;
struct {bool operator ()(int a,int b){return a>b;}};
priority_queue<int> A;
priority_queue<int,vector<int>,cmp> B;
int n,m;
int main()
{
scanf("%d",&n);
for(int i=1,x;i<=n;i++)
{
scanf("%d",&x);
B.push(x);
}
while (B.size()>A.size())
{
A.push(B.top());
B.pop();
}
scanf("%d",&m);
for(int i=1,x;i<=m;i++)
{
char str[10];
scanf("%s",str);
if (str[0]=='a')
{
scanf("%d",&x),n++;
x>A.top()?B.push(x):A.push(x);
while (A.size()>n/2)
{
B.push(A.top());
A.pop();
}
while (B.size()>A.size())
{
A.push(B.top());
B.pop();
}
}
else printf("%dn",A.top());
}
return 0;
}
|
近期评论