BOJ 2696 : 중앙값 구하기

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/2696

 

 

문제의 원리는 가운데를 말해요와 같다.

 

차이점은

 

매 tc마다 heap을 초기화

그리고 최초 입력을 받고 홀수 번째 입력부터 가운데 값을 출력

한 줄에 10개씩 출력

 

이다.

#include <stdio.h>

int T, M;

int minHeap[100100];
int minHn;

int maxHeap[100100];
int maxHn;

int maxPop(int* heap, int& hn)
{
	int tmp, ret;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--] = -10001;

	for (int i = 1; i * 2 <= hn;)
	{
		if (heap[i] > heap[i * 2] && heap[i] > heap[i * 2 + 1]) break;
		else if (heap[i * 2] > heap[i * 2 + 1])
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void maxPush(int* heap, int& hn, int x)
{
	int tmp;

	heap[++hn] = x;

	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2] > heap[i]) break;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

int minPop(int* heap, int& hn)
{
	int tmp, ret;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--] = 10001;

	for (int i = 1; i * 2 <= hn;)
	{
		if (heap[i] < heap[i * 2] && heap[i] < heap[i * 2 + 1]) break;
		else if (heap[i * 2]< heap[i * 2 + 1])
		{
			tmp = heap[i * 2];
			heap[i * 2] = heap[i];
			heap[i] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i * 2 + 1];
			heap[i * 2 + 1] = heap[i];
			heap[i] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void minPush(int* heap, int& hn, int x)
{
	int tmp;

	heap[++hn] = x;

	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2] < heap[i]) break;

		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

int main(void)
{
	scanf("%d", &T);

	for (int tc = 0; tc < T;tc++)
	{
		int mid, num, cnt;

		scanf("%d", &M);
		printf("%d\n", M / 2 + 1);

		scanf("%d", &mid);
		printf("%d ", mid);

		minHn = maxHn = 0; /* heap 초기화 */

		cnt = 1;
		for (int i = 0; i < (M - 1) / 2;i++)
		{
			scanf("%d", &num);

			if (num > mid) 
			{
				maxPush(maxHeap, maxHn, mid);
				minPush(minHeap, minHn, num);
			}
			else 
			{
				minPush(minHeap, minHn, mid);
				maxPush(maxHeap, maxHn, num);
			}

			scanf("%d", &num);

			if (maxHeap[1] <= num && num <= minHeap[1]) mid = num;
			else if (minHeap[1] < num) 
			{
				mid = minPop(minHeap, minHn);
				minPush(minHeap, minHn, num);
			}
			else
			{
				mid = maxPop(maxHeap, maxHn);
				maxPush(maxHeap, maxHn, num);
			}

			printf("%d ", mid);
			
			cnt++;

			if (cnt == 10)
			{
				putchar('\n');
				cnt = 0;
			}
		}

		putchar('\n');
	}

	return 0;
}