萌新求助,对顶堆写挂了
查看原帖
萌新求助,对顶堆写挂了
198719
洛璟楼主2021/3/7 21:06

我把 if (q.size() - 1 > qq.size()) 换成 if (q.size()== qq.size()+2) 之后就不会re了,为啥……

同时我还全WA了,球球大佬了呜呜呜,孩子快不行了klkl

#include<bits/stdc++.h>
using namespace std;
int t, n;
priority_queue<int> q;
priority_queue<int, vector<int>, greater<int> >qq;
inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c>'9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 3) + (x << 1) + (c ^ '0');
        c = getchar();
    }
    return x * f;
}
int main()
{
    t = read();
    while (t--)
    {
        while (1)
        {
            n = read();
            if (n == 0)
            {
                break;
            }
            if (n == -1)
            {
                printf("%d\n", q.top());
                q.pop();
            }
            else q.push(n);
            if (q.size() - 1 > qq.size())
            {
                int qwq = q.top();
                q.pop();
                qq.push(qwq);
            }
            if (q.size() < qq.size())
            {
                int qwq = qq.top();
                qq.pop();
                q.push(qwq);
            }
            if (!q.empty() && !qq.empty() && qq.top() < q.top())
            {
                int a = qq.top();
                int b = q.top();
                q.pop();
                qq.pop();
                q.push(a);
                qq.push(b);
            }
        }
    }
    return 0;
}
2021/3/7 21:06
加载中...