BAEKJOON 2696 - Running Median

문제: https://www.acmicpc.net/problem/2696

문제

For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far. 

입력

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by an odd decimal integer M, (1 ≤ M ≤ 9999), giving the total number of signed integers to be processed. The remaining line(s) in the dataset consists of the values, 10 per line, separated by a single space. The last line in the dataset may contain less than 10 values. 

출력

For each data set the first line of output contains the data set number, a single space and the number of medians output (which should be one-half the number of input values plus one). The output medians will be on the following lines, 10 per line separated by a single space. The last line may have less than 10 elements, but at least 1 element. There should be no blank lines in the output.

예제 입력 

3
9
1 2 3 4 5 6 7 8 9
9
9 8 7 6 5 4 3 2 1
23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56

예제 출력 

5
1 2 3 4 5
5
9 8 7 6 5
12
23 23 22 22 13 3 5 5 3 -3
-7 -3

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2009 Greater New York Programming Contest D번

각 홀수번 마다 정수가 1개 또는 2개가 입력되고 그때마다 정렬을 해서 가운데 숫자를 출력해주어야 되기 때문에 균형 이진 트리이며 값이 삽입될 때 마다 정렬이 되는 set 을 이용해 풀었습니다.

하지만 수열에 중복된 숫자가 입력되지 않는다는 조건이 없기 때문에 multiset 을 사용해야 됩니다. 전 여기서 한 번 틀렸네요.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
#include <set>
using namespace std;
 
int main()
{
    int cases, m, n;
    multiset<int> numbers;
    multiset<int>::iterator iter;
    cin >> cases;
    for (int c = 0; c < cases; c++)
    {
        cin >> m;
        int* arr = new int[m];
        for (int i = 0; i < m; i++)
            cin >> arr[i];
        int n = m / 2 + 1;
        cout << n << endl;
        numbers.clear();
        for (int i = 0; i < m; i += 2)
        {
            if (i != 0)
                numbers.insert(arr[i - 1]);
            numbers.insert(arr[i]);
            iter = numbers.begin();
            for (int j = 1; j <= i / 2; j++)
                iter++;
            cout << *iter;
            if (i != 0 && (i + 2) % 20 == 0 && i != m - 1)
                cout << endl;
            else if (i != m - 1)
                cout << " ";
        }
        cout << endl;
        delete[] arr;
    }
 
    return 0;
}