poj 1442

迷南。 2022-07-15 12:23 112阅读 0赞

<table style="font-family:&quot;Times New Roman&quot;"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center; font-size:18pt; font-weight:bold; color:blue">
      Black Box 
    </div> 
    <div style="text-align:center; font-size:12pt"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
        <td>&nbsp;</td> 
        <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;11478</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;4669</td> 
       </tr> 
      </tbody> 
     </table> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Description</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt">
      Our Black Box represents a primitive database. It can save an integer array and has a special i variable. At the initial moment Black Box is empty and i equals 0. This Black Box processes a sequence of commands (transactions). There are two types of transactions:&nbsp; 
     <br> 
     <br> ADD (x): put element x into Black Box;&nbsp; 
     <br> GET: increase i by 1 and give an i-minimum out of all integers containing in the Black Box. Keep in mind that i-minimum is a number located at i-th place after Black Box elements sorting by non- descending. 
     <br> 
     <br> Let us examine a possible sequence of 11 transactions:&nbsp; 
     <br> 
     <br> Example 1&nbsp; 
     <br> 
     <pre>N Transaction i Black Box contents after transaction Answer

(elements are arranged by non-descending)

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   </pre> 
     <br> It is required to work out an efficient algorithm which treats a given sequence of transactions. The maximum number of ADD and GET transactions: 30000 of each type.&nbsp; 
     <br> 
     <br> 
     <br> Let us describe the sequence of transactions by two integer arrays:&nbsp; 
     <br> 
     <br> 
     <br> 1. A(1), A(2), ..., A(M): a sequence of elements which are being included into Black Box. A values are integers not exceeding 2 000 000 000 by their absolute value, M &lt;= 30000. For the Example we have A=(3, 1, -4, 2, 8, -1000, 2).&nbsp; 
     <br> 
     <br> 2. u(1), u(2), ..., u(N): a sequence setting a number of elements which are being included into Black Box at the moment of first, second, ... and N-transaction GET. For the Example we have u=(1, 2, 6, 6).&nbsp; 
     <br> 
     <br> The Black Box algorithm supposes that natural number sequence u(1), u(2), ..., u(N) is sorted in non-descending order, N &lt;= M and for each p (1 &lt;= p &lt;= N) an inequality p &lt;= u(p) &lt;= M is valid. It follows from the fact that for the p-element of our u sequence we perform a GET transaction giving p-minimum number from our A(1), A(2), ..., A(u(p)) sequence.&nbsp; 
     <br> 
     <br> 
     <br> 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Input</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt">
      Input contains (in given order): M, N, A(1), A(2), ..., A(M), u(1), u(2), ..., u(N). All numbers are divided by spaces and (or) carriage return characters. 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Output</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt">
      Write to the output Black Box answers sequence for a given sequence of transactions, one number each line. 
    </div> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Input</p> <pre style="font-family:&quot;Courier New&quot;,Courier,monospace; font-size:12pt">7 4
3 1 -4 2 8 -1000 2
1 2 6 6</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Sample Output</p> <pre style="font-family:&quot;Courier New&quot;,Courier,monospace; font-size:12pt">3
3
1
2</pre> <p style="font-size:18pt; font-weight:bold; color:blue">Source</p> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt"> 
     <a href="http://poj.org/searchproblem?field=source&amp;key=Northeastern+Europe+1996" style="text-decoration:none" rel="nofollow">Northeastern Europe 1996</a> 
    </div> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt"> 
     <br> 
    </div> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt"> 
     <br> 
    </div> 
    <div style="font-family:&quot;Times New Roman&quot;,Times,serif; font-size:12pt"> 
     <br> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

#include<cstdio>
    #include<cstdlib>
    #include<queue>
    using namespace std;
    
    int main()
    {
    
        int c,n,m,x;
        int a[300003];
        while(~scanf("%d %d",&n,&m))
        {
            c=0;
            priority_queue< int,vector<int>,less<int> >p;//大顶堆
            priority_queue< int,vector<int>, greater<int> >q;//小顶堆一直维护大顶堆的最小
            for(int i=0; i<n; i++)
            {
                scanf("%d",&a[i]);
            }
            while(m--)
            {
    
                scanf("%d",&x);
                while(c<x)
                {
    
                    q.push(a[c]);
                    c++;
    
                }
                while(!p.empty()&&p.top()>q.top())
                {
    
                    int t=p.top();
                    p.pop();
                    p.push(q.top());
                    q.pop();
                    q.push(t);
    
                }
                printf("%d\n",q.top());
                p.push(q.top());
                q.pop();
    
            }
        }
    
        return 0;
    
    }

ps: 此部分是当时查题解时，找到的解释，感觉给了自己很大的助力

给出的例子  
7 4  
3 1 -4 2 8 -1000 2  
1 2 6 6  
前1个数中第1小的数是3；  
前2个数中第2小的数是3；  
前6个数中第3小的数是1；  
前6个数中第4小的数是2；  
怎么来做呢用的就是维护好两个堆，堆用优先队列来实现。  
一个最大堆，一个最小堆。最大堆意思就是最大的元素在堆顶；最大堆存的是前i-1  
小的数，那么最小堆的堆顶不就是要输出的第i小的数吗。  
在这里我们用一个循环循环的作用就是每一次往最大堆离放i-1(或者i反正就是那么个  
意思)个元素，代表前i-1小的数，那么我们循环里面再套一个while循环，因为你是在  
1-u\[p\]这么多元素里找最小值，这些元素总得输入吧。每输入一个数据先放到q1(小)里  
那么放进去之后堆顶元素就是这些数据当中最小的，如果最小的那个数比最大堆的堆顶  
元素小，说明前i-1个最小的数据需要更新，只要将小堆堆顶和大堆堆顶元素交换即可。  
那么在输出的时候同样，一个for循环结束后，最大堆的前i-1个最小的需要增至i个直接  
把最小堆的堆顶元素赋值给最小堆最大堆堆顶弹出，