题解 SP16254 【RMID2 - Running Median Again】

### 双倍经验：SP15376 题意：动态维护中位数 维护两个堆，一个大根堆，一个小根堆，每个堆存储序列中的n/2个数 大根堆存第1 - cnt/2大的数，小根堆存第cnt/2+1 - cnt大的数 例如: 插入 5 2 3 1 4 大根堆：2 1 小根堆：3 4 5 当cnt为偶数时，中位数就是小根堆的堆顶 当cnt为奇数时，中位数就是小根堆堆顶和大根堆堆顶，取最小值即可 每次插入的时候和当前中位数比较，如果比中位数大就插入小根堆，否则插入大根堆 任何时候，当两个堆大小不平衡时（大根堆>小根堆 或 小根堆>大根堆+1），就将一个堆的堆顶取出放 到另一个堆里 **这种做法有个名字：对顶堆** $Code:$ ``` #include<cstdio> #include<queue> using namespace std; priority_queue<int>p; //大根堆 存储第1-mid priority_queue<int,vector<int>,greater<int> >q; //小根堆 存储第mid+1-n int temp,cnt,t; //cnt为当前序列的数的数量 int main(){ scanf("%d",&t); while(t){ scanf("%d",&temp); if(temp==0){ //清空 while(!q.empty()) q.pop(); while(!p.empty()) p.pop(); cnt=0; t--; } else if(temp==-1){ //删除堆顶元素 if(cnt&1){ printf("%d\n",q.top()); q.pop(); } else{ //由于下面的调整，大根堆的堆顶元素一定不大于小根堆堆顶元素 printf("%d\n",p.top()); p.pop(); } cnt--; } else{ //插入 int mid=(q.empty())?0:q.top(); if(temp>mid) q.push(temp); else p.push(temp); cnt++; if((cnt&1)&&p.size()>q.size()){ //大根堆 > 小根堆 int temp0=p.top(); p.pop(); q.push(temp0); } else if((cnt&1)==0&&q.size()>p.size()){ //小根堆 > 大根堆+1 int temp0=q.top(); q.pop(); p.push(temp0); } } } return 0; } ```