模拟小根堆

当堆大小超过 k 时，pop掉堆顶元素
堆顶元素就是第 k 大的数

#include<bits/stdc++.h>
using namespace std;
#define ioio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl "\n"
#define P pair
#define P1 first
#define P2 second
#define u_map unordered_map
#define p_queue priority_queue
typedef long long ll;
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e6 + 7;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
/*-------------------------------------*/

int n,m;
int h[N],ind,cnt;

void down(int x){
   int t=x;
   if(2*x<=ind&&h[2*x]<h[t])t=2*x;
   if(2*x+1<=ind&&h[2*x+1]<h[t])t=2*x+1;
   if(t!=x){
   	swap(h[x],h[t]);
   	down(t);
   }
}
void up(int x){
   int t=x;
   if(x/2>=1&&h[x/2]>h[x])t=x/2;
   if(t!=x){
   	swap(h[x],h[t]);
   	up(t);
   }
}
void pop(){
   h[1]=h[ind];
   ind--;
   down(1);
}
void push(int x){
   h[++ind]=x;
   up(ind);
}
int main(){
   ioio
   cin>>n>>m;
   string op;
   int x;
   while(n--){
   	cin>>op;
   	if(op=="I"){
   		cin>>x;
   		push(x);
   		cnt++;
   		if(cnt>m)pop();
   	}
   	else {
   		cout<<h[1]<<endl;
   	}
   }
   return 0;
}

#include<bits/stdc++.h>
using namespace std;
int t,n,x;
char a;
int main(){
	std::ios::sync_with_stdio(false);
	priority_queue<int,vector<int>,greater<int> > num;//小顶堆 
	cin>>t>>n;
	while(t--){
		cin>>a;
		if(a=='I'){
			cin>>x;
			if(num.size()<n)
				num.push(x);
			else if(num.top()<x){//当数目大于n是，判断后面的数是否大于队列中最小的数 
				num.pop();///若小于则没必要加入队列(这样极大的优化了代码)
				num.push(x);//若大于，则先出队一个元素，再入队，保持队列中只有n个元素 
			}
		}else{
			cout<<num.top()<<endl;
		}
	}
	return 0;
}