对顶堆的模板题
对顶堆为一个大根堆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; }
|
近期评论