<백준> 2696

중앙값 구하기

문제
어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.
예를 들어, 수열이 1, 5, 4, 3, 2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.

입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다.

출력
각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t,m;

	cin >> t;

	while (t--)
	{
		cin >> m;
		priority_queue<int, vector<int>> pq;
		priority_queue<int, vector<int>, greater<int>> minpq;
		vector<int> v;
		for (int i = 0; i < m; i++)
		{
			int value;
			cin >> value;

			if (pq.size() == minpq.size())
				pq.push(value);
			else
				minpq.push(value);

			if (!pq.empty() && !minpq.empty() && pq.top() > minpq.top())
			{
				int a = pq.top(); pq.pop();
				int b = minpq.top(); minpq.pop();

				pq.push(b);
				minpq.push(a);
			}
			if (i % 2 == 0)
			{
				v.push_back(pq.top());
			}
		}
		cout << v.size() << "\n";
		for (int i = 0; i < v.size(); i++)
		{
			if (i > 0 && i % 10 == 0)
				cout << "\n";
			cout << v[i] << " ";
		}
		cout << "\n";
	}
	return 0;
}