글 읽기 - 시간초과 질문 입니다(c)

swjwpower 3년 전 0

c라서 stl은 못써서.. min heap이랑 Max heap 둘다 만들면 서로 동기화 하는 시간떄문에 시간초과 날거라 생각해서

제가 생각한 방법은 max heap 기반에 최솟값을 찾는 것인데

max heap이면 어짜피 최솟값은 맨 아랫줄에 있으니까

최댓값은 그냥 맨 위엣값 뽑고 최솟값은 아랫줄 훑어서 뽑고 다시 upheap으로 정렬하는 방법을 택했는데..

일단 제가 몆가지 넣었을땐 잘 나오는데

이게 느려서 시간초과가 나는건지.. 무한루프에 걸린건지..

그냥 시간초과라면 이 방법으론 못할까요? ㅠ

#pragma warning (disable:4996)
#include <stdio.h>
#include <stdlib.h>

void change(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void upheap(int heap[], int index) {
	while (index > 1) {
		if (heap[index] > heap[index / 2]) change(&heap[index], &heap[index / 2]);
		index /= 2;
	}
}

void addlast(int heap[], int* index, int x) {
	heap[*index] = x;
	upheap(heap, *index);
	(*index)++;
}

void delMax(int heap[], int* index) {
	int x = heap[1], cur = 1, bigger;
	if (*index != 1) {
		//printf("%d\n", x);
		heap[*index] = 0;
		(*index)--;
		heap[1] = heap[*index];
		while (cur < *index - 1) {
			bigger = heap[cur * 2] < heap[cur * 2 + 1] ? cur * 2 + 1 : cur * 2;
			if (heap[cur] > heap[bigger]) break;
			else {
				change(&heap[cur], &heap[bigger]);
			}
			cur = bigger;
		}
	}
}

int findMinIndex(int heap[], int index) {
	int cur = index, smaller = heap[index], smallIndex = index;
	while (cur > index / 2) {
		cur--;
		if (smaller > heap[cur]) {
			smaller = heap[cur];
			smallIndex = cur;
		}
	}
	return smallIndex;
}


void delMin(int heap[], int* index) {
	int x = heap[1], cur = 1, bigger;
	if (*index != 1) {
		(*index)--;
		cur = findMinIndex(heap, *index);
		//printf("%d", heap[cur]);
		change(&heap[cur], &heap[*index]);
		upheap(heap, cur);
		heap[*index + 1] = 0;
	}
}

int main() {
	int heap[20000] = { 0 }, x, N, index = 1, T;
	char order;
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &N);
		getchar();
		while (N--) {
			scanf("%c %d", &order, &x);
			getchar();
			if (order == 'I') {
				addlast(heap, &index, x);
			}
			else {
				if (x == 1) {
					delMax(heap, &index);
				}
				else {
					delMin(heap, &index);
				}
			}
		}
		if (index != 1) {
			printf("%d %d\n", heap[1], heap[findMinIndex(heap, index)]);
		}
		else printf("EMPTY\n");
		index = 1;
	}
}

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

문제

문제

출처

ICPC

시간초과 질문 입니다(c)

swjwpower 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말