UVA501 Black Box

题解 数据结构-堆 提高+/省选-
题目链接 编辑文章

题意

要求维护一个序列,可以动态插入和查询第 $k$ 大。

命令总数 $\le 30000$ 。

题解

用两个堆维护,大根堆大小为 $k-1$ ,其余放入小根堆。

  1. 插入操作时,先插入大根堆,然后取堆顶放入小根堆。
  2. 查询操作时,答案就是小根堆顶,并将答案放入大根堆。
#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int t,n,m,add[30005],Get[30005];

signed main()
{
    t=read();
    while (t--)
    {
        priority_queue <int> mx;
        priority_queue <int,vector<int>,greater<int> > mn;
        n=read(); m=read();
        for (int i=1;i<=n;i++) add[i]=read();
        for (int i=1;i<=m;i++) Get[i]=read();
        int j=1;
        for (int i=1;i<=n;i++)
        {
            mx.emplace(add[i]);
            mn.emplace(mx.top());
            mx.pop();
            while (Get[j]==i && j<=m)
            {
                printf("%d\n",mn.top());
                mx.emplace(mn.top());
                mn.pop();
                j++;
            }
        }
        if (t) puts("");
    }
    return 0;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。