【解題】What is the Median?

ACM Volume CI 10107 - What is the Median?


The Problem

Median plays an important role in the world of statistics. By definition, it is a value which divides an array into two equal parts. In this problem you are to determine the current median of some long integers.

Suppose, we have five numbers {1,3,6,2,7}. In this case, 3 is the median as it has exactly two numbers on its each side. {1,2} and {6,7}.

If there are even number of values like {1,3,6,2,7,8}, only one value cannot split this array into equal two parts, so we consider the average of the middle values {3,6}. Thus, the median will be (3+6)/2 = 4.5. In this problem, you have to print only the integer part, not the fractional. As a result, according to this problem, the median will be 4!


Input

The input file consists of series of integers X ( 0 <= X < 2^31 ) and total number of integers N is less than 10000. The numbers may have leading or trailing spaces.


Output

For each input print the current value of the median.


Sample Input

1
3
4
60
70
50
2


Sample Output

1
2
3
3
4
27
4


解題思考

　　這一題要求我們輸出「到每筆輸入資料為止的中位數」。我的方法很直觀，也許還太笨了點。

　　其實就是每次輸入一筆資料之後，就把該筆資料插入到數列中適合的地方，使數列永遠是已排序狀態的。

　　接著，就直接透過索引值，輸出中位數就可以了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    int x, num[10000], n = 0;
    while (cin >> x)
    {
        // 將新輸入的數字插入到適合的位置
        int i = (n++) - 1;
        while (i >= 0 && num[i] > x)
        {
            num[i + 1] = num[i];
            i--;
        }

        num[i + 1] = x;


        // 找出中位數
        int mid = n / 2;
        if (n % 2)
        {
            cout << num[mid] << endl;
        }
        else
        {
            cout << (num[mid] + num[mid - 1]) / 2 << endl;
        }
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}