首页 > 代码库 > wikioi 2573 大顶堆与小顶堆并用

wikioi 2573 大顶堆与小顶堆并用

题目描述 Description

我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻,黑匣子为空且i等于0。这个黑匣子能执行一系列的命令。有两类命令:

ADD(x):把元素x放入黑匣子;GET:把i加1的同时,输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素已非降序排序后位于第i位的元素。

下面的表6_4是一个11个命令的例子:

表6_4

编号

命令

i

黑匣子内容

输出

1

ADD(3)

0

3

 

2

GET

1

3

3

3

ADD(1)

1

1,3

 

4

GET

2

1,3

3

5

ADD(-4)

2

-4,1,3

 

6

ADD(2)

2

-4,1,2,3

 

7

ADD(8)

2

-4,1,2,3,8

 

8

ADD(-1000)

2

-1000,-4,1,2,3,8

 

9

GET

3

-1000,-4,1,2,3,8

1

10

GET

4

-1000,-4,1,2,3,8

2

11

ADD(2)

4

-1000,-4,1,2,2,3,8

 

现需要一个有效的算法处理给定的一系列命令。ADD和GET命令的总数至多个有30000个。定义ADD命令的个数为M个,GET命令的个数为N个。我们用下面得两个整数序列描述命令序列:

1.A(1),A(2),……,A(M):加入黑匣子的元素序列。所有的数均为绝对值不超过2000000的整数。例如在上例中A=(3,1,-4,2,8,-1000,2)。

2.u(1),u(2),……,u(N):u(i)表示第i个GET命令在第u(i)个ADD命令之后,例如在上例中,u=(1,2,6,6)。

你可以假定自然数序列u(1),u(2),……,u(N)以非降序排列,N≤M,且对于每一个p(1≤p≤N)有p≤u(p)≤M。

输入描述 Input Description

第一行存放M和N的值,第二行存放 A(1),A(2),……,A(M) ,第三行存放u(1),u(2),……,u(N)。

输出描述 Output Description

输出黑匣子的处理结果。

样例输入 Sample Input

7 4

3 1 -4 2 8 -1000 2

1 2 6 6

样例输出 Sample Output

3

3

1

2


刚开始并不知道这题该如何下手,知道是堆做了。但是具体也不知道怎么做。

看了这第二个解题报告了才知道如何做:http://www.wikioi.com/solution/list/2573/(第二个解题报告,思想很好)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<bitset>
#define INF 100007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
priority_queue<int,vector<int>,greater<int> >heap_small;
priority_queue<int>heap_big;
int a[30005],b[30005];
int main()
{
    int n,k,i,j,ii=0,jj=-1;
    cin>>n>>k;
    for(i=1; i<=n; i++)
        scanf("%d",a+i);
    for(i=0; i<k; i++)
        scanf("%d",b+i);
    for(i=1; i<=n; i++)
    {
        if(jj<ii) heap_big.push(a[i]),jj++;
        else
        {
            int ans=heap_big.top();
            if(a[i]>=ans) heap_small.push(a[i]);
            else
            {
                heap_big.pop();
                heap_small.push(ans);
                heap_big.push(a[i]);
            }
        }
        while(i==b[jj])
        {
            printf("%d\n",heap_big.top());
            ii++;
            if(jj+1<k&&i==b[jj+1])
            {
                int ans=heap_small.top();
                heap_small.pop();
                heap_big.push(ans);
                jj++;
            }
            else break;
        }
        if(ii>=k) break;
    }
    return 0;
}