poj_1442_Black Box_优先队列

lzusa 发布于 2019-04-23 893 次阅读


题目大意

有两个数列,一个为add,一个为get,每次从add里取一个数加入数列,然后每到数列的长度在get中时,输出数列中前x个数中的最小值,没get,x加一

思路

开两个队列,一个升序,一个降序,每次往里面插入数,并进行是否大于x的判断,如果到了get中的数时,输出堆顶并累加x
O(2*m*logm)

#include 
#include 
int a[100000],b[100000];
using namespace std;
priority_queue heap;
priority_queue,greater > heap1;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for (int i=1;i<=m;i++)
        scanf("%d",&b[i]);
    int i=0,j=1,k=1;
    while (j<=m)
    {
        if (i==b[j])
        {
            j++;
            if (heap.size()a[i])   
            {
                heap1.push(heap.top());
                heap.pop();
                heap.push(a[i]);
            }
            else heap1.push(a[i]);
        }
    }
    return 0;
}
]]>