fork download 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <queue>
  4.  
  5. using std::vector;
  6. using std::greater;
  7. using std::less;
  8. using std::make_heap;
  9. using std::push_heap;
  10. using std::pop_heap;
  11.  
  12. // Удаляет элемент из min-кучи и возвращает его
  13. int remove_from_min(vector<int>& heap)
  14. {
  15. 	pop_heap(heap.begin(), heap.end(), greater<int>());
  16. 	int tmp = heap.back();
  17. 	heap.pop_back();
  18. 	return tmp;
  19. }
  20.  
  21. // Удаляет элемент из max-кучи и возвращает его
  22. int remove_from_max(vector<int>& heap)
  23. {
  24. 	pop_heap(heap.begin(), heap.end(), less<int>());
  25. 	int tmp = heap.back();
  26. 	heap.pop_back();
  27. 	return tmp;
  28. }
  29.  
  30. // Добавление нового элемента в min-кучу
  31. void push_to_min(vector<int>& heap, int value)
  32. {
  33. 	heap.push_back(value);
  34. 	push_heap(heap.begin(), heap.end(), greater<int>());
  35. }
  36.  
  37. // Добавление нового элемента в max-кучу
  38. void push_to_max(vector<int>& heap, int value)
  39. {
  40. 	heap.push_back(value);
  41. 	push_heap(heap.begin(), heap.end(), less<int>());
  42. }
  43.  
  44. // Балансирование размеров куч. Если размеры отличаются на 2,
  45. // перекидываем элемент из одной кучи в другую
  46. void balance_heaps(vector<int>& min, vector<int>& max)
  47. {
  48. 	int tmp;
  49. 	if(min.size() < max.size())
  50. 	{
  51. 		tmp = remove_from_max(max);
  52. 		push_to_min(min, tmp);
  53. 	}
  54. 	if(min.size() > max.size())
  55. 	{
  56. 		tmp = remove_from_min(min);
  57. 		push_to_max(max, tmp);
  58. 	}
  59. }
  60.  
  61. // Прочитанный из входного потока элемент добавляется в одну из двух куч.
  62. // При этом производится балансирование размеров
  63. void push_new_value(vector<int>& min, vector<int>& max, int value)
  64. {
  65. 	push_to_min(min, value);
  66. 	int diff = min.size() > max.size() ? min.size() - max.size()
  67. 									   : max.size() - min.size();
  68. 	if(diff == 2)
  69. 		balance_heaps(min, max);
  70. }
  71.  
  72. // Вычисление медианы среди всех элементов.
  73. // Если число элементов четное, медиана вычисляется как средне арифметическое
  74. // двух центральных элементов в упорядоченной последовательности
  75. double find_median(vector<int>& min, vector<int>& max)
  76. {
  77. 	if(min.size() == max.size())
  78. 	{
  79. 		pop_heap(min.begin(), min.end(), greater<int>());
  80. 		pop_heap(max.begin(), max.end(), less<int>());
  81. 		return (min.back() + max.back()) / 2.0;
  82. 	}else{
  83. 		pop_heap(min.begin(), min.end(), greater<int>());
  84. 		return min.back();
  85. 	}
  86. }
  87.  
  88. int main()
  89. {
  90. 	std::vector<int> min_heap;
  91. 	std::vector<int> max_heap;
  92.  
  93. 	int value;
  94. 	while(std::cin >> value)
  95. 	{
  96. 		push_new_value(min_heap, max_heap, value);
  97. 		std::cout << std::setprecision(2) << find_median(min_heap, max_heap) << std::endl;
  98. 	}
  99. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin 
1
2
3
4
5
6
7
8
9
10
stdout 
1
1.5
2
2.5
4
3
5
5
5
7.5
https://ideone.com/XsEekf
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!