글 읽기 - 최대 힙 반례 부탁드립니다

rookel 5년 전 0

나름대로 반례 만들어봤지만 자꾸 틀렸습니다가 뜨네요

반례좀 부탁드립니다.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int heap[200002], cnt;
int main()
{
	int N, k;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &k);
		if (k == 0) {
			if (cnt == 0) printf("0\n");
			else {
				printf("%d\n", heap[1]);

				int next = 1;
				while (next <= cnt) {
					int left = next * 2;
					int right = next * 2 + 1;

					next = (heap[left] > heap[right]) ? left : right;
					heap[next / 2] = heap[next];
					heap[next] = 0;
				}
				cnt--;
			}
		}
		else {
			heap[++cnt] = k;
			int current = cnt;
			while (current > 1) {
				int parent = current / 2;
				if (heap[current] > heap[parent]) {
					int tmp = heap[current];
					heap[current] = heap[parent];
					heap[parent] = tmp;
				}
				else {
					break;
				}
				current /= 2;
			}
		}
	}
	return 0;
}

rookel 5년 전 0

해결했습니다.

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

문제

문제

출처

ICPC

최대 힙 반례 부탁드립니다

rookel 5년 전 0

rookel 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말