洛谷3871 [TJOI2010]中位数维护队列的中位数

题目描述

给定一个由N个元素组成的整数序列，现在有两种操作：

1 add a

在该序列的最后添加一个整数a，组成长度为N + 1的整数序列

2 mid 输出当前序列的中位数

中位数是指将一个序列按照从小到大排序后处在中间位置的数。（若序列长度为偶数，则指处在中间位置的两个数中较小的那个）

例1：1 2 13 14 15 16 中位数为13

例2：1 3 5 7 10 11 17 中位数为7

例3：1 1 1 2 3 中位数为1

输入输出格式

输入格式：

第一行为初始序列长度N。第二行为N个整数，表示整数序列，数字之间用空格分隔。第三行为操作数M，即要进行M次操作。下面为M行，每行输入格式如题意所述。

输出格式：

对于每个mid操作输出中位数的值

输入输出样例

输入样例#1：

6

1 2 13 14 15 16

5

add 5

add 3

mid

add 20

mid

输出样例#1：

5

13

说明

对于30%的数据，1 ≤ N ≤ 10,000，0 ≤ M ≤ 1,000

对于100%的数据，1 ≤ N ≤ 100,000，0 ≤ M ≤ 10,000

序列中整数的绝对值不超过1,000,000,000，序列中的数可能有重复

每个测试点时限1秒

解法

维护中位数，两个堆

发现题解大神有拿 sort+二分查找暴力出奇迹A题的，还有主席树的。

操作就是

你需要一个大根堆和一个小根堆，小根堆里面放前 N/2 个大的数，大根堆里面放后 N-N/2 大的数

这样就能保证堆顶就是中位数

在插入的时候，把大于堆顶的扔到小根堆否则扔到大根堆

当然我们还要维护使得两个堆大小最多差1

废话

懒得写堆当然要用priority了

小根堆写法priority_queue<int,vector<int>,greater<int> > 或者你也可以机智的把数先变成负的直接扔进priority_queue里当小根堆用

#include<bits/stdc++.h>

using namespace std;

int N,Q,cnt;

char s[];

priority_queue <int> q1,q2;

int add()

{

    cnt++;

    int x;

    scanf("%d",&x);

    if(q2.empty())q2.push(x);

    else if(x<q2.top())q2.push(x);

    else q1.push(-x);

    while(q2.size()>cnt-cnt/){

        int tmp=-q2.top();q2.pop();

        q1.push(tmp);

    }

    while(q1.size()>cnt/){

        int tmp=-q1.top();q1.pop();

        q2.push(tmp);

    }

}

int main()

{

    scanf("%d",&N);

    for(int i=;i<=N;i++)add();

    scanf("%d",&Q);

    while(Q--){

        scanf("%s",s);

        if(s[]=='a')add();

        else printf("%d\n",q2.top());

    }

    return ;

}

吐槽

我永远也不想回到教室学习电磁感应和基因突变

巴特西

洛谷3871 [TJOI2010]中位数维护队列的中位数

题目描述

输入输出格式

输入输出样例

说明

解法

废话

吐槽

最新文章

热门文章

巴特西

洛谷3871 [TJOI2010]中位数 维护队列的中位数

题目描述

输入输出格式

输入输出样例

说明

解法

废话

吐槽

最新文章

热门文章

洛谷3871 [TJOI2010]中位数维护队列的中位数