FF_pigeon @ 2022-12-01 20:12:34

#include<bits/stdc++.h>
using namespace std;
int n,a;
priority_queue<int> dg;
priority_queue<int,vector<int>,greater<int> > xg;
int main()
{
    cin >> n;
    cin >> a;
    dg.push(a);
    cout << dg.top() << endl;
    for(int i=2;i<=n;i++)
    {
        cin >> a;
        if(a>dg.top())xg.push(a);
        else dg.push(a);
        int u=xg.size(),v=dg.size();
        while(abs(u-v)>1)
        {

            if(u>v)
            {
                xg.push(dg.top());
                dg.pop();
            } 
            else
            {
                dg.push(xg.top());
                xg.pop();
            }
            u=xg.size(),v=dg.size();
        }
        if(i%2==1)
        {
            if(v>u)cout << dg.top() << endl;
            else cout << xg.top() << endl;
        }
    }
    return 0;
}

by a2lyaXNhbWUgbWFyaXNh @ 2022-12-01 20:23:23

#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

inline void write(int x) {
    if(x<0)
        putchar('-'),x=-x;
    if(x>9) {
        write(x/10);
    }
    putchar(x%10 +'0');
}

vector<int>v;

int n;
int main() {
    n=read();
    for(int i=1;i<=n;i++){
        int x=read();
        v.insert(upper_bound(v.begin(),v.end(),x),x);
        if(i%2){
            write(v[(i-1)/2]);
            puts("");
        }
    }
    return 0;
}

by FF_pigeon @ 2022-12-01 20:28:41

我以我肤浅的知识看出这是二分 （也就看出了二分）

by FF_pigeon @ 2022-12-01 20:58:13

有没有哪位大佬可以指正一下为啥会TLE

by Code_星云 @ 2022-12-01 21:23:35

@wangchengxi
你代码RE的原因大概率是在执行pop函数的时候某个堆里面根本没有值，STL都要注意这一点。
其次，TLE 的原因可能是 while 出了问题。考虑到这道题每次循环内都会维护一次堆，所以只需要 if 就可以了。
再者，你楼上的那个代码是用 vector 维护了一个类似平衡树（你可以理解为 set）的数据结构,lower_bound是找前/后节点。

#include<bits/stdc++.h>
using namespace std;
int n,a;
priority_queue<int> dg;
priority_queue<int,vector<int>,greater<int> > xg;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a;
        if(!dg.size()||a<dg.top())dg.push(a);
        else xg.push(a);
        if(dg.size()&&dg.size()>=xg.size()+2){
            xg.push(dg.top());
            dg.pop();
        }
        if(xg.size()&&xg.size()>=dg.size()+2)
        {
            dg.push(xg.top());
            xg.pop();
        }
        if(i%2==1)
        {
            if(dg.size()>xg.size())cout << dg.top() << endl;
            else cout << xg.top() << endl;
        }
    }
    return 0;
}

by FF_pigeon @ 2022-12-06 20:57:39

谢谢大佬QWQ