poj1442~优先队列oye

历经磨难终于解决了这题，原来用stl可以这么简单~

这题的思路:

用stl弄2个优先队列，big队列优先弹出最小的，small队列优先弹出最大的，若要求第i小的数字，只要满足small队列里有i个元素，且small队列的top比big队列的top小，则small的top就是第i小的数字。

关于优先队列记住下面这些东西：

模板原型：

priority_queue<T,Sequence,Compare>

T:存放容器的元素类型

Sequence:实现优先级队列的底层容器，默认是vector<T>

Compare:用于实现优先级的比较函数，默认是functional中的less<T>，即默认是弹出最大的元素

若要创建弹出最小元素的优先队列，形式是priority_queue<int,vector<int>,greater<int> >big;

比较函数当然可以自己去定义。

常用的操作如下：

empty()  如果优先队列为空，则返回真 
pop()  删除第一个元素 
push()  加入一个元素 
size()  返回优先队列中拥有的元素的个数 
top()  返回优先队列中有最高优先级的元素 

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include <vector>
#include<set>
#define M 30005
using namespace std;
int a[M],u[M];


int main()
{
priority_queue<int,vector<int>,greater<int> >big; //优先弹出 小元素 的 big队列
priority_queue<int>small; //优先弹出大元素的small队列
int m,n,i,j,t1,t2;
cin>>m>>n;
for(i=1;i<=m;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
scanf("%d",&u[i]);
j=1;
for(i=1;i<=n;i++)
{
for(;j<=u[i];j++) //先统一放入big队列
big.push(a[j]);

while(small.size()<i) //若要知道第i小，small队列里必须要有i个元素
{
small.push(big.top()); //进行转移
big.pop();
}
while(!big.empty()&&small.top()>big.top()) //若small队列里的top是答案的话，那么必须满足
{ //small里大的小于big里最小的
t1=small.top(); //若不满足，就进行交换直到满足
t2=big.top();
small.pop();
big.pop();
small.push(t2);
big.push(t1);
}
printf("%d\n",small.top());
}
return 0;
}