灌水&疑问

xianjing @ 2023-11-09 22:47:04

by lovely_Rex @ 2023-11-13 15:54:35

对顶堆是O(nlogn)的,本题n有5000000,会T

by xianjing @ 2023-11-29 20:41:29

@wuhaojun 可是我没t啊 芝士代码(开了O2

#include <bits/stdc++.h>
using namespace std;
int cnt(){
    int x;
    scanf("%d",&x);
    return x;
}
signed main(){
    int n,k;
    scanf("%d %d",&n,&k);
    priority_queue<int>l;
    priority_queue<int, vector<int>, greater<int> >b;
    for(int i=0;i<n;i++){
        if(l.size()<=k){
            l.push(cnt());
        }
        else{
            b.push(cnt());
        }

        if(l.empty()||b.empty()){
            continue;
        }
        while(l.top()>b.top()){
            b.push(l.top());l.push(b.top());
            l.pop();b.pop();
        }
    }
    printf("%d",l.top());
    return 0;
}