优先队列的一种使用方法 bjfuoj1310

描述

Alice找Bob玩一个数字游戏：
每一回合中，Alice有两个选择，要么在纸上写上一个数字，要么问Bob现在纸上第k大的数和第k小的数分别是多少，当然，当纸上的数少于k个的时候，Alice是不会问的。
Bob觉得这游戏实在太无聊了，所以决定写个程序来陪Alice玩，请你帮帮他。

输入

输入包含多组测试数据。
每组数据的第一行包含两个整数N和K（1<=K<=N<=1000000）。接下来是N行，每行要么是一个字符'I'接着一个32位整数d，表示Alice在纸上写下d，要么是一个字符'Q'，表示Alice问Bob现在纸上第K大的数和第K小的数分别是多少。

输出

对于Alice的每一次询问，请在一行内输出结果，格式详见样例。

样例输入

8 3
I 1
I 2
I 3
Q
I 5
Q
I 4
Q

样例输出

1 3
2 3
3 3

思路：

    输入一个排序一次肯定不行，会超时。只能用更高级的方法，优先队列。这里定义两个有限队列a,b，一个从小到大，另一个从大到小。当输入的数比k多的时候就直接pop掉，然后最顶层的就会是最大值或者最小值。

代码：

 #include<iostream>
#include<stdio.h>
#include<functional>
#include<queue>
using namespace std;
priority_queue<long long int, vector<long long int>, less<long long int> > a; // da -> xiao
priority_queue<long long int, vector<long long int>, greater<long long int> > b;
// xiao->da
int main()
{
int n,k;char ch[2];
long long x;
//
freopen("Data.txt","r",stdin);
while(scanf("%d%d",&n,&k)!=EOF){
while(!a.empty())
a.pop();
while(!b.empty())
b.pop();
for(int z=0;z<n;z++){
scanf(" %s",ch);
if(ch[0]=='I'){
scanf("%I64d",&x);
a.push(x);
b.push(x);
if(a.size()>k){
a.pop();
}
if(b.size()>k){
b.pop();
}
}
else if(ch[0]=='Q'){
printf("%I64d %I64dn",b.top(),a.top());
}
}
}
//
getchar();
return 0;
}