重庆建设部网站官网网站开发核心技术
Description
给定一个长度为 NN 的非负整数序列 AA，对于前奇数项求中位数。
Input
第一行一个正整数 NN。
第二行 NN 个正整数 A1…NA1…N。
Output
共 ⌊N+12⌋⌊2N+1⌋ 行，第 ii 行为 A1…2i−1A1…2i−1 的中位数。
Sample 1
| Inputcopy | Outputcopy |
|---|---|
7 1 3 5 7 9 11 6 | 1 3 5 6 |
Sample 2
| Inputcopy | Outputcopy |
|---|---|
7 3 1 5 9 8 7 6 | 3 3 5 6 |
Hint
对于 20%20% 的数据，N≤100N≤100；
对于 40%40% 的数据，N≤3000N≤3000；
对于 100%100% 的数据，1≤N≤1000001≤N≤100000，0≤Ai≤1090≤Ai≤109。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int n;
int main() {ios::sync_with_stdio(false); // 禁用同步cin.tie(nullptr); // 解除cin与cout绑定cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}vector<int> m;for (int i = 1; i <= n; i ++) {if (i == 1) {m.insert(m.begin(), a[i]);}else {int x = 0, y = m.size();while (x < y) {int mid = (x + y) / 2;if (m[mid] > a[i]) {y = mid;}else {x = mid + 1;}}m.insert(m.begin() + x, a[i]);}if (i % 2 == 1) {cout << m[m.size() / 2] << endl;}}return 0;
}