中位数

中位数

【40 分】$O(n^2\log n)$ 的暴力

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000 + 5];
vector<int> t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i += 2)
    {
        // 求前 i 项的中位数
        t.clear();
        for (int j = 1; j <= i; j++)
            t.push_back(a[j]);
        sort(t.begin(), t.end());
        cout << t[t.size() / 2] << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000 + 5];
vector<int> t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i += 2)
    {
        sort(a + 1, a + i + 1);
        cout << a[i / 2 + 1] << "\n";
    }
    return 0;
}

【60 分】利用插入排序的 $O(n^2)$

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000 + 5];
vector<int> t;
void f(int pos)
{
    // 把 a[pos] 插入到 a[1]~a[pos-1] 中的合适位置
    while (pos > 1 && a[pos] < a[pos - 1])
    {
        swap(a[pos], a[pos - 1]);
        pos--;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i += 2)
    {
        if (i == 1)
        {
            cout << a[1] << "\n";
            continue;
        }
        f(i - 1); // 把 a[i-1] 插入到 a[1]~a[i-2] 的合适位置
        f(i);     // 把 a[i] 插入到 a[1]~a[i-1] 的合适位置
        cout << a[i / 2 + 1] << "\n";
    }
    return 0;
}

【100 分】对顶堆的 $O(n\log n)$ 做法

#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000 + 5];
priority_queue<int> small, big;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i += 2)
    {
        if (i == 1)
            small.push(a[i]);
        else
        {
            // a[i-1]放进对顶堆
            if (a[i - 1] <= small.top())
                small.push(a[i - 1]);
            else
                big.push(-a[i - 1]);
            // a[i]放进对顶堆
            if (a[i] <= small.top())
                small.push(a[i]);
            else
                big.push(-a[i]);
            // 协调两边，保证左边的大小比右边大一个
            while (big.size() > small.size())
            {
                small.push(-big.top());
                big.pop();
            }
            while (small.size() > big.size() + 1)
            {
                big.push(-small.top());
                small.pop();
            }
        }
        cout << small.top() << "\n";
    }
    return 0;
}

【100 分】利用多重集的满分

需要注意：如果 s.insert(x) 时，multiset 中之前有 x，那么会插入到之前的 x 的后面。

#include <bits/stdc++.h>
using namespace std;
int n, a[112345];
multiset<int> s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    s.insert(a[1]);
    auto it = s.begin();
    cout << a[1] << "\n";
    for (int i = 2; i + 1 <= n; i += 2)
    {
        if (a[i] > a[i + 1])
            swap(a[i], a[i + 1]);
        s.insert(a[i]);
        s.insert(a[i + 1]);
        int now = (*it);
        if (now <= a[i])
            it++;
        else if (a[i + 1] < now)
            it--;
        cout << (*it) << "\n";
    }
    return 0;
}

【100 分】可以但没必要的利用离散化+数据结构的做法

离散化+权值树状数组+第 k 名查询

直接二分套树状数组，${\log }^{2}n$ 查询。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n;
int a[MAXN + 5];
int temp[MAXN + 5];
// 权值树状数组
int t[MAXN + 5];
int lowbit(int x)
{
    return x & (-x);
}
// a[x]++
void add(int x)
{
    for (int i = x; i <= n; i += lowbit(i))
        t[i]++;
}
int query(int x)
{
    int res = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        res += t[i];
    return res;
}
int kth(int x)
{
    int l = 1;
    int r = n;
    int ans = -1; // 找到第一个前缀和大于等于 x 的位置
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (query(mid) >= x)
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 离散化：a[i] 替换为了对应的排名（从1开始）
    // temp[i] 是离散化后的i在离散化之前的数
    for (int i = 1; i <= n; i++)
        temp[i] = a[i];
    sort(temp + 1, temp + n + 1);
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(temp + 1, temp + n + 1, a[i]) - temp;
    // 树状数组求中位数
    add(a[1]);
    cout << temp[a[1]] << "\n";
    for (int i = 3; i <= n; i += 2)
    {
        add(a[i - 1]);
        add(a[i]);
        cout << temp[kth((i + 1) / 2)] << "\n";
    }
    return 0;
}

$\log n$ 查询

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n, log2n;
int a[MAXN + 5];
vector<int> temp;
// 权值树状数组
int t[MAXN + 5];
int lowbit(int x)
{
    return x & (-x);
}
void add(int x)
{
    for (int i = x; i <= n; i += lowbit(i))
        t[i]++;
}
int kth(int x)
{
    int pos = 0, cnt = 0;
    for (int i = log2n; i >= 0; i--)
    {
        pos += (1 << i);
        if (pos > n || cnt + t[pos] >= x)
            pos -= (1 << i);
        else
            cnt += t[pos];
    }
    return pos + 1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    log2n = log2(n);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 离散化：a[i] 替换为了对应的排名（从1开始）
    // temp[i-1] 是离散化后的i在离散化之前的数
    for (int i = 1; i <= n; i++)
        temp.push_back(a[i]);
    sort(temp.begin(), temp.end());
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(temp.begin(), temp.end(), a[i]) - temp.begin() + 1;
    // 树状数组求中位数
    add(a[1]);
    cout << temp[a[1] - 1] << "\n";
    for (int i = 3; i <= n; i += 2)
    {
        add(a[i - 1]);
        add(a[i]);
        cout << temp[kth((i + 1) / 2) - 1] << "\n";
    }
    return 0;
}