P7072 [CSP-J2020] 直播获奖 对顶堆

对顶堆动态维护第k大的值。

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
     int n,w;
     cin>>n>>w;
     priority_queue<int,vector<int>,greater<int>> minq;
     priority_queue<int> maxq;

     int k=0;
     auto update=[&](){
        if(minq.size()<k){
          minq.push(maxq.top());
          maxq.pop();
        }
        if(minq.size()>k){
          maxq.push(minq.top());
          minq.pop();
        }
     };

     auto push=[&](int x){
        if(x>maxq.top()){
          minq.push(x);
        }else{
          maxq.push(x);
        }
        update();
     };
     
     maxq.push(0);
     for(int i=1;i<=n;i++){
         int x;
         cin>>x;
         k=max(1,i*w/100);
         push(x);
         cout<<minq.top()<<" ";
     }

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}