BOJ 11286 : 절댓값 힙

삼성 B형 전체 링크

 

www.acmicpc.net/problem/11286

 

 

우선순위가 최소 힙, 최대 힙보다 조금 더 까다롭다.

 

1) 절댓값이 가장 작으면 우선순위가 높다.

2) 같은 절댓값인 경우는 음수가 우선순위가 높다.

 

따라서, 최악의 값은 양수 중에 가장 큰 값이 된다.

if / else if의 비교를 함수로 만들면 편하다.

heap[hn--] = 0x7fff0000; /* 최악의 값은 양수 중 가장 큰 값 */

int abs(int x)
{
	return (x > 0) ? x : -x;
}

int isMin(int a, int b)
{
	if (abs(a) < abs(b)) return 1; /* 절댓값 중 작으면 우선순위가 크다 */
	if (abs(a) == abs(b) && a < b) return 1; /* 같은 절댓값이면 음수가 우선순위가 크다 */

	return 0;
}

 

if (heap[i / 2] <= heap[i]) break;

→ if (isMin(heap[i / 2], heap[i])) break; 로 바꿔서 사용하면 된다.

#include <stdio.h>

int N;
int heap[100100];
int hn;

int abs(int x)
{
	return (x > 0) ? x : -x;
}

int isMin(int a, int b)
{
	if (abs(a) < abs(b)) return 1;
	if (abs(a) == abs(b) && a < b) return 1;

	return 0;
}

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

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--] = 0x7fff0000;

	for (register int i = 1; i * 2 <= hn;)
	{
		if (isMin(heap[i], heap[i * 2]) && isMin(heap[i], heap[i * 2 + 1])) break;
		else if (isMin(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 push(int* heap, int& hn, int x)
{
	register int tmp;

	heap[++hn] = x;

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

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

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

	for (int i = 0; i < N;i++)
	{
		int x;
		scanf("%d", &x);
		if (x) push(heap, hn, x);
		else
		{
			if (hn) printf("%d\n", pop(heap, hn));
			else printf("0\n");
		}
	}

	return 0;
}