洛谷刷题之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;
}