专栏首页glm的全栈学习之路对顶堆求区间k小(大)数

对顶堆求区间k小(大)数

P1801 黑匣子_NOI导刊2010提高(06)

首先,这道题让我们求每次的第i大值,而i是会移动的——那我们就可以理解为,我们需要知道第i大值和第i+1大值(请撕烤)。那用什么数据结构呢?

  • 首先,要确定第i大值,就可以知道i-1~1是从大到小的;
  • 相似的,i+1~n的元素是从小到大的。
  • 可以用堆来完成

我们用一个大根堆来保存前i-1大数,大根堆确定了其中的元素是从大到小的;再用一个小根堆来存剩下的数,小根堆堆顶就是第i大数。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    char ch=getchar();int s=0,w=1;
    while(ch<48||ch>57){if(ch=='-')w=-1;ch=getchar();}
    while(ch>=48&&ch<=57){s=s*10+ch-48;ch=getchar();}
    return s*w;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
int m,n;
int a[200005],b[200005];
priority_queue<int>maxx;
priority_queue<int,vector<int>,greater<int> >minn;
int main()
{
m=read(),n=read();
for(register int i=1;i<=m;i++)
{
    a[i]=read();
}
for( register  int i=1;i<=n;i++)
{
    b[i]=read();
}
int l=1,r;
for( register int i=1;i<=n;i++)
{
    r=b[i];
    for(register int j=l;j<=r;j++)
    {
        maxx.push(a[j]);
        if(maxx.size()>=i)
        {
            minn.push(maxx.top());
            maxx.pop();
        }
    }
    l=r+1;
    cout<<minn.top()<<endl;
    maxx.push(minn.top());
    minn.pop();
}
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 八皇后递归实现

    八皇后问题,是指在8X8d的棋盘上放置八个皇后,使得她们不能互相攻击,皇后的攻击范围是同行同列,或是在一条对角线上,满足...

    glm233
  • 排序算法之我观

    笔者今年是xmu大一新生 9月初学编程 学到泡排的时候就对排序这一块深入了解 (也只是很粗浅地学习了一下) 写这篇文章的初衷就是复习一下之前所学,有不足...

    glm233
  • Python Tips(1) 数字与字符串之间转换,采用内置函数

    glm233
  • HDU 3018 Ant Trip(欧拉回路)

    #include <bits/stdc++.h> using namespace std; const int N=100005; int f[N]; ...

    用户2965768
  • 51Nod-1149-Pi的递推式

    ACM模版 描述 ? 题解 image.png 代码 #include <cstdio> #include <algorithm> #include <cmat...

    f_zyj
  • HDU 2011 菜鸟杯

    A:该题写了很久,一直TLE,主要是枚举到n/2时间复杂度实在太高了,其实嘛,这道题就是因式分解,所以就是i*i=n,也就是sqrt(n) #include<s...

    用户1624346
  • 西南民族大学程序竞赛

    No matter what activities you join,whether you want or not, you could gain unexp...

    AngelNH
  • CSU1216: 异或最大值(01Trie树)

    多组数据。第一行为数字个数n,1 <= n <= 10 ^ 5。接下来n行每行一个32位有符号非负整数。

    attack
  • BZOJ3265: 志愿者招募加强版(线性规划)

    attack
  • 招商银行校招题一

    小招喵喜欢吃喵粮。这里有 N 堆喵粮,第 i 堆中有 p[i] 粒喵粮。喵主人离开了,将在 H 小时后回来。

    黑白格

扫码关注云+社区

领取腾讯云代金券