POJ 1442 Black Box（优先队列+对顶堆）（破镜重圆小说）

POJ 1442 Black Box（优先队列+对顶堆）（破镜重圆小说）

​​传送门​​

题目大意

有一些ADD和GET操作。n次ADD操作，每次往序列中加入一个数，由ADD操作可知序列长度为1-n时序列的组成。GET操作输入一个序列长度，输出当前长度序列第i大的元素的值。i初始为0，每次GET操作i先加1。给出的GET操作输入非降。

思路

对顶堆 大根堆维护小于当前需询问的节点的值 小根堆维护大于当前需询问的节点的值 那么大根堆的size等于当前询问的节点时，大根堆的堆顶就是答案。

代码

ll u[maxn],a[maxn];//小根堆维护大于等于当前节点的数//大根堆维护小于当前节点的数//然后来回抛 priority_queue,greater > qx;priority_queue qd;int main(){ int m,n; scanf("%d%d",&m,&n); for(int i=1;i<=m;i++){ scanf("%lld",&a[i]); } for(int i=1;i<=n;i++){ scanf("%lld",&u[i]); } int x=0;//当前节点值 int cnt=1; for(int i=1;i<=m;i++){ if(qd.size()==0){ qd.push(a[i]); } else{ if(a[i]x){ qx.push(qd.top()); qd.pop(); } else{ qd.push(qx.top()); qx.pop(); } } ll xx=qd.top(); printf("%lld\n",xx); } } }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。