题目描述

给定一个长度为N的非负整数序列A，对于前奇数项求中位数。

输入格式
第一行一个正整数N,
第二行N个正整数

输出格式
共N/2+1行

样例

输入

7
1 3 5 7 9 11 6

输出

1
3
5
6

算法1

(树状数组) $O(nlogn)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int tr[N],cnt[N];
int n;
struct innt {
    int id, num;
}a[N];
int lowbit(int x)
{
    return x & -x;
}
void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i))tr[i] += c;
}
int query(int x)
{
    int res = 0;
    for(int i=x;i;i-=lowbit(i))res+=tr[i];
    return res;
}
bool cmp(innt a, innt b)
{
    if (a.num == b.num)return a.id < b.id;
    return a.num < b.num;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].num; a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    //先从小到大排序
    for (int i = 1; i <= n; i++)cnt[a[i].id] = i;
    //离散化，后续根据1到n的序号来代替数从小到大的序号
    add(cnt[1], 1);
    cout << a[cnt[1]].num<<endl;
    //先加入并输出第一个数，因为第一个数不需要和后面的比较
    for (int i = 2; i <= n; i++)
    {
        add(cnt[i], 1);
        if (i & 1)//如果是奇数
        {
            int l = 1, r = n; int mid=0;
            //利用二分法来查找
            while (l < r)
            {
                mid = l + r >> 1;
                int u = i/2+1;
                //取中间值+1
                if (query(mid)<u)l = mid + 1;
                else r = mid;
            }
            cout <<a[l].num<< endl;
            //输出符合条件的数，并把他还原成原数值,因为在树状数组上的顺序就是原数组从小到大的排序，而在输入a数组之后我们就已经从小到大排序了，所以这个时候a数组的下标所对应的num就是原数值
        }
    }
    return 0;
}

算法2

(优先队列) $O(logn)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
priority_queue<int>deue1;//大根堆
priority_queue<int,vector<int>,greater<int>>deue2;//小根堆

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    int x; cin >> x;
    cout << x << endl;
    int mid = x;
    for (int i = 2; i <= n; i++)
    {
        cin >> x;
        if (x > mid)deue2.push(x);//小根堆储存比他大的数
        else deue1.push(x);//大根堆储存比他小的数
        if (i % 2)
        {
            if (deue1.size() > deue2.size())
            {
                int num = deue1.top();
                deue1.pop();
                deue2.push(mid);
                cout << num << endl;
                mid = num;
            }
            else if (deue1.size() < deue2.size())
            {
                int num = deue2.top();
                deue2.pop();
                deue1.push(mid);
                cout << num << endl;
                mid = num;
            }
            else cout << mid << endl;
        }
    }
    return 0;
}