median maintenance

median.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>


int main()
{
	std::ifstream input_file("D:\\Playground\\Median.txt");
	std::vector<int> x, m, h1, h2;
	std::make_heap(h1.begin(), h1.end());
	std::make_heap(h2.begin(), h2.end(),[](auto a,auto b)
	{
		return a > b;
	});
	int t;
	while (input_file >> t)
	{
		if (h1.empty()|| t<h1.front())
		{
			h1.push_back(t);
			std::push_heap(h1.begin(), h1.end());
		}
		else
		{
			h2.push_back(t);
			std::push_heap(h2.begin(), h2.end(), [](auto a, auto b)
			{
				return a > b;
			});
		}

		if(h2.size()>h1.size())
		{
			h1.push_back(h2.front());
			std::push_heap(h1.begin(), h1.end());

			std::pop_heap(h2.begin(), h2.end(), [](auto a, auto b)
			{
				return a > b;
			});
			h2.pop_back();
		}
		else if (h1.size() - h2.size() >= 2)
		{
			h2.push_back(h1.front());
			std::push_heap(h2.begin(), h2.end(), [](auto a, auto b)
			{
				return a > b;
			});

			std::pop_heap(h1.begin(), h1.end());
			h1.pop_back();
		}
		m.push_back(h1.front());
	}

	int r=0;
	for (auto&& i : m)
	{
		r += i;
	}
	std::cout << r % 10000 << std::endl;
	system("pause");
	return 0;
}