题意

• 输入一个序列，每当该序列元素个数为奇数个的时候，就输出中位数

思路

• 对顶堆维护整个序列，大顶堆维护前一半，小顶堆维护后一半，如果进入的元素比小顶堆的堆顶小，就放入大顶堆
• 每次放完元素后维护两个堆，使奇数个时小顶堆的元素个数总比大顶堆多1，这样子中位数就在小顶堆的堆顶，输出即可

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;;
	scanf("%d",&t);
	while(t--){
		int idx,n;
		scanf("%d%d",&idx,&n);
		priority_queue<int,vector<int>,greater<int>>a;//小顶堆
		priority_queue<int,vector<int>,less<int>>b;//大顶堆
		int cnt=0;
        printf("%d %d\n",idx,n/2+1);
		for(int i=1;i<=n;i++){
			int tp;
			scanf("%d",&tp);
			if(!a.empty()&&tp<a.top()) b.push(tp);
			else a.push(tp);
			
			while(a.size()-b.size()>1){
				b.push(a.top());
				a.pop();
			}
			while(a.size()-b.size()<1){
				a.push(b.top());
				b.pop();
			}
			if((a.size()+b.size())%2){
				printf("%d ",a.top());
				cnt++;
				if(cnt%10==0||i==n){
					printf("\n");
				}
			}
			
		}
		
	}
	
	return 0;
}

priority_queue

• priority_queue<类型>名称

• priority_queue<类型,vector<类型>,比较方法>名称

• 比较方法包含：

  大顶堆：less<类型>

  小顶堆：greater<类型>

  自定义：结构体重载

  struct cmp {
    bool operator()(const int& a, const int& b) {
        return a>b;//无限制 
    }
  };
  

• 方法：

  top():队首

  size():大小

  empty():空

  push():插入

  pop():踢出队首