uva 501 - Black Box(优先队列)

题目链接：uva 501 - Black Box

题目大意：有一个集合，给定元素进入集合的顺序，现在有Q次查询，给定每次查询在第几个元素进入集合后，对于每i次查询，输出集合中第i小的数。

解题思路：用两个优先队列维护，队列a优先出值大的，队列b优先出值小的，在第i次询问前，保证a队列中有i-1个元素元素，并且抱枕都比b中的小，然后每次询问输出b队列的首元素，并且将它放到a队列中。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int maxn = 30005; int N, M, arr[maxn], v[maxn]; void solve () { priority_queue
       
         a; priority_queue
        
         , greater
         
           > b; for (int i = 1; i <= N; i++) { a.push(arr[i]); b.push(a.top()); a.pop(); while (v[i]--) { printf("%d\n", b.top()); a.push(b.top()); b.pop(); } } } int main () { int cas; scanf("%d", &cas); while (cas--) { int x; memset(v, 0, sizeof(v)); scanf("%d%d", &N, &M); for (int i = 1; i <= N; i++) scanf("%d", &arr[i]); for (int i = 0; i < M; i++) { scanf("%d", &x); v[x]++; } solve(); if (cas) printf("\n"); } return 0; }