UVa 10107 What is the Median?

本文主要是介绍UVa 10107 What is the Median?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

10107 - What is the Median?

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1048

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

完整代码：

/*0.035s*/#include<cstdio>int a[10010];int main()
{int i, x, cnt = 0, m;while (~scanf("%d", &x)){for (i = cnt; i; i--){if (a[i] > x) a[i + 1] = a[i];else break;}a[i + 1] = x;++cnt;m = cnt >> 1;printf("%d\n", (cnt & 1 ? a[m + 1] : (a[m] + a[m + 1]) >> 1));}return 0;
}

PS：使用 Treap 复杂度更低。

这篇关于UVa 10107 What is the Median?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---