fork download
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <queue>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using std::vector;
  8. using std::greater;
  9. using std::less;
  10.  
  11. class RunningMedian
  12. {
  13. private:
  14. std::priority_queue<int> max_heap;
  15. std::priority_queue<int, vector<int>, greater<int>> min_heap;
  16.  
  17. public:
  18. void push(int value)
  19. {
  20. // adding the number into the proper heap
  21. if(max_heap.empty())
  22. max_heap.push(value);
  23. else{
  24. if(value >= max_heap.top())
  25. min_heap.push(value);
  26. else
  27. max_heap.push(value);
  28. }
  29. // balancing heaps
  30. if (max_heap.size() - min_heap.size() == 2)
  31. {
  32. min_heap.push(max_heap.top());
  33. max_heap.pop();
  34. }
  35. else if (min_heap.size() - max_heap.size() == 2)
  36. {
  37. max_heap.push(min_heap.top());
  38. min_heap.pop();
  39. }
  40. }
  41.  
  42. double median()
  43. {
  44. if (max_heap.size() == min_heap.size())
  45. return (max_heap.top() + min_heap.top()) / 2.0;
  46. else if (max_heap.size() > min_heap.size())
  47. return max_heap.top();
  48. else
  49. return min_heap.top();
  50. }
  51. };
  52.  
  53. int main(){
  54. RunningMedian solver;
  55. int n, value;
  56.  
  57. std::cin >> n;
  58. for(int i = 0; i < n; i++)
  59. {
  60. std::cin >> value;
  61. solver.push(value);
  62. std::cout << std::fixed << std::setprecision(2) << solver.median() << std::endl;
  63. }
  64. return 0;
  65. }
Success #stdin #stdout 0s 3464KB
stdin
10
1
2
3
4
5
6
7
8
9
10
stdout
1.00
1.50
2.00
2.50
3.00
3.50
4.00
4.50
5.00
5.50