P1801-黑匣子_NOI导刊2010提高（06）

小灰灰 2023-06-01 08:55 20阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 #define MOD 1000000007
     6 #define pb push_back
     7 #define maxn 200003 
     8 typedef long long ll;
     9 using namespace std;
    10 inline ll read()
    11 {
    12     ll ans = 0;
    13     char ch = getchar(), last = ' ';
    14     while(!isdigit(ch)) last = ch, ch = getchar();
    15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    16     if(last == '-') ans = -ans;
    17     return ans;
    18 }
    19 inline void write(ll x)
    20 {
    21     if(x < 0) x = -x, putchar('-');
    22     if(x >= 10) write(x / 10);
    23     putchar(x % 10 + '0');
    24 }
    25 int N,M;
    26 priority_queue<int> pqd;
    27 priority_queue<int,vector<int>,greater<int>> pqx;
    28 int in1[maxn];
    29 int in2[maxn];
    30 void balance()
    31 {
    32     if(pqx.size() && pqd.size())
    33     while(pqx.top()<pqd.top())
    34     {
    35         int a = pqx.top();
    36         int b = pqd.top();
    37         pqx.pop();pqd.pop();
    38         pqx.push(b);
    39         pqd.push(a);
    40     }
    41 }
    42 int main()
    43 {
    44     N = read(),M = read();
    45     _for(i,1,N+1)
    46         in1[i] = read();
    47     _for(i,1,M+1)
    48         in2[i] = read();
    49     
    50     int st = 1;
    51     _for(i,1,M+1)
    52     {
    53         while(pqd.size()+pqx.size()<in2[i])
    54             pqx.push(in1[st++]);
    55         pqd.push(pqx.top());
    56         pqx.pop();
    57         balance();
    58         printf("%d\n",pqd.top());
    59     }
    60     return 0;
    61 }

转载于:https://www.cnblogs.com/Asurudo/p/11557759.html