글 읽기 - 1655 c언어 코드를 어떻게 고쳐야 할지 모르겠네요ㅠ

wjdrjseh 2년 전 0

지금 반례는

5
1
0
2
-1
3

입니다.

어떻게 고쳐야 할까요?

//	 [ 반례 ]	 [ 정답 ]	[ 내 출력 ]
//		5			1 			1
//		1 			0 			0
//		0 			1 			1
//		2 			0 			-1
//		-1 			1 			1
//		3 			

#include <stdio.h>
#include <stdlib.h>
#define MAX_COUNT 200001


int N;
typedef struct
{
	int data[MAX_COUNT];
	int size;
} Heap;


void push_max(Heap* h, int value)
{
	{
		int idx;

		h->size++;
		idx = h->size;
		h->data[idx] = value;

		while((idx!=1) && (h->data[idx/2]<h->data[idx]))
		{
			int tmp;

			tmp = h->data[idx/2];
			h->data[idx/2] = h->data[idx];
			h->data[idx] = tmp;

			idx /= 2;
		}
	}
}
void push_min(Heap* h, int value)
{
	{
		int idx;

		h->size++;
		idx = h->size;
		h->data[idx] = value;

		while((idx!=1) && (h->data[idx/2]>h->data[idx]))
		{
			int tmp;

			tmp = h->data[idx/2];
			h->data[idx/2] = h->data[idx];
			h->data[idx] = tmp;

			idx /= 2;
		}
	}
}


int main(void)
{
	Heap max_heap;
	Heap min_heap;

	max_heap.size = 0;
	min_heap.size = 0;


	int * input = (int*)malloc((MAX_COUNT) * sizeof(int));
	int * output = (int*)malloc((MAX_COUNT) * sizeof(int));

	for(int i=0; i<MAX_COUNT; i++) max_heap.data[i] = -100005;
	for(int i=0; i<MAX_COUNT; i++) min_heap.data[i] = 100005;
	

	scanf("%d", &N);
	for(int i=0; i<N; ++i)
		scanf("%d", &input[i]);


	for(int i=0; i<N; ++i)
	{
		if(i%2 == 0)
			push_max(&max_heap, input[i]);
		else
			push_min(&min_heap, input[i]);

		if(i>=1 && max_heap.data[1]>min_heap.data[1])
		{
			int tmp;

			tmp = max_heap.data[1];
			max_heap.data[1] = min_heap.data[1];
			min_heap.data[1] = tmp;
		}

		output[i] = max_heap.data[1];
	}

	for(int i=0; i<N; ++i)
		printf("%d\n", output[i]);

	return 0;
}

zenith82114 2년 전 0

-1 들어갈 때 틀리는 이유는

지금 max힙에 있는 최솟값보다도 작은 애가 min힙에 들어가기 때문인데요.

어느 힙에 넣는지는 무조건 번갈아서가 아니라 각 힙의 top이 지금 얼마인지 보고 판단해야 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1655 c언어 코드를 어떻게 고쳐야 할지 모르겠네요ㅠ

wjdrjseh 2년 전 0

zenith82114 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말