洛谷P1168 中位数

考察优先队列。

中位数 - 洛谷

建一个大根堆和一个小跟堆，对于第一个元素，我们把它设为mid值，第一个元素的中位数就是它本身，继续输入下一个元素，如果它大于mid就把它存在"小"根堆里，如果它小于mid就把它存在小根堆里，当i为奇数时，因为大根堆递增，小根堆递减，如果大根堆中元素个数与小根堆相同，那么mid就是中位数，如果不相同，就把mid往元素多的一边挪一挪，1.将mid，push到元素少的那边，取出元素多的那边赋值给mid，然后pop，这样mid就是中位数了。

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<unordered_map>
#include<sstream>
#include<map>
#include <array>
#include <string>
#include<numeric>
#include<set>
#include <random>
#include <unordered_set>
#include <iomanip>
#include <climits>
#include<string.h>

using i64 = long long;
int mid;
std::priority_queue<i64, std::vector<i64>, std::less<i64>>q1;
std::priority_queue<i64, std::vector<i64>, std::greater<i64>>q2;//小根堆
int main() {
	i64 n,x;
	std::cin >> n;
	std::cin >> x;
	mid = x;
	std::cout << x << '\n';
	for (int i = 2; i <= n; i++) {
		std::cin >> x;
		if (x > mid)q2.push(x);
		else q1.push(x);
		if (i & 1) {
			while (q1.size() != q2.size()) {
				if (q1.size() > q2.size()) {
					q2.push(mid);
					mid = q1.top();
					q1.pop();
				}
				else {
					q1.push(mid);
					mid = q2.top();
					q2.pop();
				}
			}
			std::cout << mid << '\n';
		}
		
	}
	return 0;
}