/*
题意:ADD(a)表示向集合中增加元素a,get表示取出第k小元素,k根据get出现的次数不断变化,出现多少次取第几小数
题解:每次取第k小元素,k不断更新。使用两个堆,来完成。
小顶堆负责,选出最小的元素
大顶堆负责,选出k个元素中最大的元素,即第k小元素
*/
#include <iostream>
using namespace std;
const int nMax = 30010;
int tree1[nMax];//大顶堆
int k1;
int tree2[nMax];//小顶堆
int k2;
int M, N;
int A[nMax];
void build1(int *tree, int k)
{
int p = k;
while(p != 1)
{
if(tree[p] > tree[p / 2])
{
int temp = tree[p];
tree[p] = tree[p / 2];
tree[p / 2] = temp;
}
p = p / 2;
}
}
void build2(int *tree, int k)
{
int p = k;
while(p != 1)
{
if(tree[p] < tree[p / 2])
{
int temp = tree[p];
tree[p] = tree[p / 2];
tree[p / 2] = temp;
}
p = p / 2;
}
}
void update1(int *tree, int k)
{
int p = 1;
while(2 * p <= k)
{
int son;
if(2 * p == k || tree[2 * p] > tree[2 * p + 1])
son = 2 * p;
else
son = 2 * p + 1;
if(tree[p] < tree[son])
{
int temp = tree[p];
tree[p] = tree[son];
tree[son] = temp;
}
p = son;
}
}
void update2(int *tree, int k)
{
int p = 1;
while(2 * p <= k)
{
int son;
if(2 * p == k || tree[2 * p] < tree[2 * p + 1])
son = 2 * p;
else
son = 2 * p + 1;
if(tree[p] > tree[son])
{
int temp = tree[p];
tree[p] = tree[son];
tree[son] = temp;
}
p = son;
}
}
int main()
{
//freopen("e://data.in", "r", stdin);
while(scanf("%d%d", &M, &N) != EOF)
{
int i;
for(i = 1; i <= M; ++ i)
scanf("%d", &A[i]);
int pre = 0;
k1 = k2 = 0;
for(i = 1; i <= N; ++ i)
{
int a;
scanf("%d", &a);
for(int j = pre + 1; j <= a; ++ j)
{
tree2[++k2] = A[j];
build2(tree2, k2);
}
pre = a;
tree1[++ k1] = tree2[1];
build1(tree1, k1);
tree2[1] = tree2[k2 --];
update2(tree2, k2);
while(k2 != 0 && tree1[1] > tree2[1])
{
int temp = tree1[1];
tree1[1] = tree2[1];
tree2[1] = temp;
update1(tree1, k1);
update2(tree2, k2);
}
printf("%d\n", tree1[1]);
}
}
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1753387
poj2823 最大最小堆实现,话说这题为啥要用最大最小堆。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
poj 1001答案