A16 对顶堆 第k大的数

20250305:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N], b[N]; 
priority_queue<LL> Q1;
priority_queue<LL, vector<LL>, greater<LL>> Q2;
int main()
{
    int n, w; scanf("%d%d", &n, &w);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    
    for(int i=1; i<=n; i++)
	{
        Q1.push(a[i]);
        
        if(!Q1.empty() &&  !Q2.empty() && Q1.top()>Q2.top())
		{
            LL x1=Q1.top();Q1.pop(); 
			LL x2=Q2.top();Q2.pop();
            Q1.push(x2);
            Q2.push(x1);
        }
    
        int t=max(1.0, floor(1.0*i*w/100));
        if(Q2.size()<t)
		{
            Q2.push( Q1.top() );
			Q1.pop();
        }
         
        printf("%lld ", Q2.top());
    }
    printf("\n");
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
LL a[N], b[N]; 
priority_queue<LL> Q1;
priority_queue<LL, vector<LL>, greater<LL>> Q2;
int main(){
    int n, w; scanf("%d%d", &n, &w);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    for(int i=1; i<=n; i++){
        Q1.push(a[i]);
        int t=max(1.0, floor(1.0*i*w/100));
        while(Q1.size()<i-t+1){
            LL x=Q2.top(); Q2.pop();
            Q1.push(x);
        }
        while(Q1.size()>i-t+1){
            LL x=Q1.top(); Q1.pop();
            Q2.push(x);
        }
         
        while(!Q2.empty() && Q1.top()>Q2.top()){
            LL x1=Q1.top(), x2=Q2.top();
            Q1.pop(); Q1.push(x2);
            Q2.pop(); Q2.push(x1);
        }
         
        printf("%lld ", Q1.top());
    }
    printf("\n");
    return 0;
}