洛谷刷题之P1168

中位数

题目描述

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

输入格式

第一行一个正整数 N N N。

第二行 N N N 个正整数 A 1 … N A_{1\dots N} A1…N​。

输出格式

共 ⌊ N + 1 2 ⌋ \lfloor \frac{N + 1}2\rfloor ⌊2N+1​⌋ 行，第 i i i 行为 A 1 … 2 i − 1 A_{1\dots 2i - 1} A1…2i−1​ 的中位数。

样例 #1

样例输入 #1

7
1 3 5 7 9 11 6

样例输出 #1

1
3
5
6

样例 #2

样例输入 #2

7
3 1 5 9 8 7 6

样例输出 #2

3
3
5
6

提示

对于 20 % 20\% 20% 的数据， N ≤ 100 N \le 100 N≤100；

对于 40 % 40\% 40% 的数据， N ≤ 3000 N \le 3000 N≤3000；

对于 100 % 100\% 100% 的数据， 1 ≤ N ≤ 100000 1 \le N ≤ 100000 1≤N≤100000， 0 ≤ A i ≤ 1 0 9 0 \le A_i \le 10^9 0≤Ai​≤109。

题解

分析

这道题我们用二分记录一下在第 i i i位时的顺序即可 , , ,因为 v e c t o r vector vector是从下标 0 0 0开始的，所以到第 i i i个数时，中位数下标 = ( i + 1 ) / 2 =(i+1)/2 =(i+1)/2
PS：上面大家可能看不懂，建议看代码

v e c t o r vector vector基本用法

v . p u s h _ b a c k ( ) v.push\_back() v.push_back()在 v e c t o r vector vector末尾插入一个数据

v . i n s e r t ( ) v.insert() v.insert()在 v e c t e r vecter vecter中插入一个元素

v . e r a s e ( ) v.erase() v.erase()在 v e c t o r vector vector中删除一个元素

Code

#include <bits/stdc++.h>

using namespace std;

vector<int> e;

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        e.insert(upper_bound(e.begin(), e.end(), x), x); //保证单调性
        if (i % 2 == 1) //判断奇数
        {
            cout << e[(i - 1) / 2] << endl; //是奇数个，就输出
        }
    }
    return 0;
}