fork download
copy 
  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 3468KB
comments (?)
stdin
copy 
10
1
2
3
4
5
6
7
8
9
10
stdout
copy 
1.00
1.50
2.00
2.50
3.00
3.50
4.00
4.50
5.00
5.50
https://ideone.com/papgI4
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!