中位数【C语言】

解题思路

#include<stdio.h> #include<stdlib.h> #define MAX_SIZE 200005 int h1[MAX_SIZE]; int n1; int h2[MAX_SIZE]; int n2; void up1(int i){ int p=(i-1)/2; while(i>0 && h1[p]<h1[i]){ int t=h1[p]; h1[p]=h1[i]; h1[i]=t; i=p; p=(i-1)/2; } } void down1(int i){ int l=2*i+1; int r=2*i+2; int m=i; if(l<n1 && h1[l]>h1[m]){ m=l; } if(r<n1 && h1[r]>h1[m]){ m=r; } if(m!=i){ int t=h1[i]; h1[i]=h1[m]; h1[m]=t; down1(m); } } void up2(int i){ int p=(i-1)/2; while(i>0 && h2[p]>h2[i]){ int t=h2[p]; h2[p]=h2[i]; h2[i]=t; i=p; p=(i-1)/2; } } void down2(int i){ int l=2*i+1; int r=2*i+2; int m=i; if(l<n2 && h2[l]<h2[m]){ m=l; } if(r<n2 && h2[r]<h2[m]){ m=r; } if(m!=i){ int t=h2[i]; h2[i]=h2[m]; h2[m]=t; down2(m); } } void push(int x){ h1[n1]=x; n1++; up1(n1-1); if(n1>n2+1){ int t=h1[0]; h1[0]=h1[n1-1]; n1--; down1(0); h2[n2]=t; n2++; up2(n2-1); }else if(n2>0 && h1[0]>h2[0]){ int t=h1[0]; h1[0]=h2[0]; h2[0]=t; down1(0); down2(0); } } int pop(){ int mid=h1[0]; h1[0]=h1[n1-1]; n1--; down1(0); if(n2>n1){ int t=h2[0]; h2[0]=h2[n2-1]; n2--; down2(0); h1[n1]=t; n1++; up1(n1-1); } return mid; } int main(){ n1=0; n2=0; char op[10]; while(scanf("%s",op)!=EOF){ if(op[0]=='p' && op[1]=='u'){ int x; scanf("%d",&x); push(x); }else if(op[0]=='p' && op[1]=='o'){ int mid=pop(); printf("%d\n",mid); } } return 0; }