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
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