Running Median http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?cid=8154&pid=1003&ojid=1

1003.cpp

#include <cstdio>
#include <set>

using namespace std;

int main()
{
	int case_count;
	scanf("%d", &case_count);
	for (int i = 1; i <= case_count; ++ i)
	{
		int n, cur;
		multiset<int> s;
		scanf("%*d%d", &n);
		printf("%d %d\n", i, ((n>>1)+1));
		for (int j = 0; j < n; ++ j)
		{
			scanf("%d", &cur);
			s.insert(cur);
			if ((j & 1) == 0)
			{
				int k;
				multiset<int>::iterator itr;
				int median_subscript = j >> 1;
				for ( k = 0, itr= s.begin(); k < median_subscript; ++ itr, ++k)
				{ }
				if (j % 20 == 0)
				{
					if (j == 0 )
						printf("%d", (*itr));
					else
						printf("\n%d", (*itr));
				}
				else
					printf(" %d", (*itr));
			}
		}
		printf("\n");
	}
	return 0;
}