颓废是人类进步的阶梯

懵逼的 题目

传送至 破甲

扯淡的 题解

po大爷blog的时候发现了这个玩意…感觉非常资瓷啊qwqwqwqwqwq

对顶堆

就是维护一个小根堆和一个大根堆, 小根堆的所有数都大于大根堆里的所有数, 插入一个数$x$就把$x$与当前的中位数比较
$$
\begin{cases}
maxq.push(x)\,\,\,\,x \le mid \\
minq.push(x)\,\,\,\,x > mid
\end{cases}
$$
然后平衡两个堆的大小, 怎么平衡? 直接暴力平衡! 每次平衡都是$\mathrm O(1)$的怂什么!

然后$size$较大的堆的堆顶就是中位数了qwq

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (10000 + 5)
using namespace std;
int n, ans[MAXN];
struct cmp1
{
    bool operator () (const int x, const int y)
    { return x < y; }
};
struct cmp2
{
    bool operator () (const int x, const int y)
    { return x > y; }
};
int main()
{
//    cout << "Hello world!" << endl;
    freopen("in.in", "r", stdin);
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d%d", &ans[0], &n);
        priority_queue<int, vector<int>, cmp1> maxq;
        priority_queue<int, vector<int>, cmp2> minq;
        int srx;
        scanf("%d", &srx);
        minq.push(srx);
        ans[1] = srx;
        for (int i = 2; i <= n; i++)
        {
            scanf("%d", &srx);
            if (srx < ans[i >> 1])    maxq.push(srx);
            else    minq.push(srx);
            while (maxq.size() > minq.size() + 1)
                minq.push(maxq.top()), maxq.pop();
            while (minq.size() > maxq.size() + 1)
                maxq.push(minq.top()), minq.pop();
            if (i & 1)
                ans[(i + 1) >> 1] = ((maxq.size() > minq.size()) ? maxq.top() : minq.top());
        }
        printf("%d %d\n", ans[0], (n + 1) >> 1);
        for (int i = 1; i <= ((n + 1) >> 1); i++)
            printf("%d%c", ans[i], (i % 10 == 0 ? '\n' : ' '));
        if (((n + 1) >> 1) % 10)
            puts("");
    }
    return 0;
}

/*
3
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56
*/

By 可能是闲得蛋疼的 Cansult