本文主要是介绍hdu 1442 Black Box，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
hdu 1442 Black Box
执行两种操作 ADD 和GET操作
ADD就是往数列中加数 GET就是获取当前数列中第i大的数（i的值为当前执行GET的次数）
ADD操作和GET操作交错进行 给出ADD和GET操作的个数 以及每次ADD操作的数 GET操作的时间
答案输出执行GET操作时得到的值
这题主要的是要输出当前数组第K大的值
用两个优先队列对ADD的数进行存储
一个队列是大值优先（用来存储已经输出过的答案 或者是后加的 比之前输出过的值更小的值）
一个队列是小值优先（用来存储添加的元素）
输出一个答案就是说明执行了一次GET操作 然后将这个答案从小值优先队列弹出加到大值优先队列中
所以在执行第K个GET操作时 大值优先队列中存储的是K-1个值
在执行往小值优先队列中加数操作之后要比较这个队列中的最小值与大值优先队列中的top 最大值的大小
确保小值优先队列中当前的top是第k大的值
代码很简单
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <queue>#define eps 1e-8
#define op operator
#define MOD 10009
#define MAXN 100100#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FOV(i,a,b) for(int i=a;i>=b;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define REV(i,a,b) for(int i=a-1;i>=b;i--)
#define MEM(a,x) memset(a,x,sizeof a)
#define ll __int64using namespace std;int a[30010];int main()
{
//freopen("ceshi.txt","r",stdin);int n,m;while(scanf("%d%d",&m,&n)!=EOF){for(int i=0;i<m;i++) scanf("%d",&a[i]);priority_queue<int,vector<int>,greater<int> > qmin;//最小值优先priority_queue<int,vector<int>,less<int> > qmax;//最大值优先int cnt=0;for(int i=0;i<n;i++){int x;scanf("%d",&x);while(cnt<x){qmin.push(a[cnt]);if(!qmax.empty()&&qmin.top()<qmax.top()){int ss=qmin.top();qmin.pop();qmax.push(ss);qmin.push(qmax.top());qmax.pop();}cnt++;}printf("%d\n",qmin.top());qmax.push(qmin.top());qmin.pop();
// cnt++;}}return 0;
}
这篇关于hdu 1442 Black Box的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
