글 읽기 - [c] 시간초과가 나옵니다...

lofri 3년 전 0

시간 초과가 나옵니다...

뭘 바꿔야 시간초과가 안나오는지 모르겠습니다 ㅠㅠ

도움주시면 감사합니다

#include <stdio.h>
#define MAX_SIZE 100001

typedef struct _maxHeap {
	long long heap[MAX_SIZE];
	int heap_size;
}maxHeap;

void initHeap(maxHeap* h) {
	h->heap_size = 0;
}

void insertHeap(maxHeap* h, int num) {
	int i;
	i = ++(h->heap_size);
	while (i != 1 && h->heap[i / 2] < num) {
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = num;
}

int deleteHeap(maxHeap* h) {
	if (h->heap_size == 0)
		return 0;
	int parent, child;
	int res = h->heap[1];
	int temp = h->heap[h->heap_size--];
	parent = 1;
	child = 2;
	while (child <= h->heap_size) {
		if (child < h->heap_size &&
			h->heap[child] < h->heap[child + 1])
			child++;
		if (temp < h->heap[child]) {
			h->heap[parent] = h->heap[child];
			parent = child;
			child *= 2;
		}
	}
	h->heap[parent] = temp;
	return res;
}

int main() {
	int n, input;
	maxHeap h;
	initHeap(&h);
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &input);
		if (input == 0) {
			printf("%d\n", deleteHeap(&h));
		}
		else {
			insertHeap(&h, input);
		}
	}
}

kth001 3년 전 0

deleteHeap의 로직이 이상합니다 그리고 잘 푼거같은데 시간초과가 나면 무한루프 한번 의심해보세요

while (child <= h->heap_size) {//what if child == h->heap_size? 
		if (child < h->heap_size &&
			h->heap[child] < h->heap[child + 1])
			child++;//weird
		if (temp < h->heap[child]) {
			h->heap[parent] = h->heap[child];
			parent = child;
			child *= 2;
		}
	}

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

문제

문제

출처

ICPC

[c] 시간초과가 나옵니다...

lofri 3년 전 0

kth001 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말