poj 1442 Black Box(堆 优先队列)

时间:2023-11-14 16:33:14

题目:http://poj.org/problem?id=1442

题意:n,m,分别是a数组,u数组的个数,u[i]w为几,就加到a几,然后输出第i 小的

刚开始用了一个小顶堆,超时,后来看了看别人的 代码,很巧妙的设计

 #include<stdio.h>
#include<queue> using namespace std; int a[];
int main()
{
int n,i,m,j,u;
priority_queue< int,vector<int>,less<int> > maxhead;
priority_queue< int,vector<int>,greater<int> > minhead;
scanf("%d %d",&n,&m);
for(i=;i<=n;i++)
scanf("%d",&a[i]);
j=;
for(i=;i<=m;i++)
{
scanf("%d",&u);
while(j<=u )
{
maxhead.push(a[j++]); //加到头大的队列里,队列里后i-1数始终是最小的
}
while(maxhead.size()>= i) //一直删到第i个数,包括i
{
minhead.push(maxhead.top());
maxhead.pop();
}
printf("%d\n",minhead.top()); //头小的第一个就是
maxhead.push(minhead.top());
minhead.pop();
}
return ;
}