글 읽기 - 힙 시간초과

phpmysql 4년 전 0

시간초과가 나길래 우선 입출력을 cin, cout -> scanf, printf 로 고쳤지만 실패해서, 알고리즘도 조금 수정해보고 노력했지만, 계속 실패하네요... 혹시 어떤 점을 개선하면 좋을까요?

#include <stdio.h>
int heap[100100], size = 0;
void swap(int* a, int* b){
	auto t = *a;
	*a = *b;
	*b = t;
}
int abs(int a){
	return (a < 0) ? -a : a;
}
void heapify(int n, int i){
    int lar = i; // lar : largest
    int left = (i << 1) + 1, right = (i + 1) << 1;
    
    if(left < n){
    	int t1 = heap[lar], t2 = heap[left];
    	if(abs(t1) > abs(t2) || (abs(t1) == abs(t2) && t1 > t2)) lar = left;
    }
    if(right < n){
    	int t1 = heap[lar], t2 = heap[right];
    	if(abs(t1) > abs(t2) || (abs(t1) == abs(t2) && t1 > t2)) lar = right;
    }
    if(lar != i){
        swap(&heap[lar], &heap[i]);
        heapify(n, lar);
    }
}
void push(int data){ // 원소 삽입
    heap[size] = data; size += 1;
    for(int i = (size>>1); i >= 0; i--){
    	heapify(size, i);
    }
}
void extract(){ // 원소 추출
	if(size <= 0){
		printf("0\n");
	}
	else{
		printf("%d\n", heap[0]);
	    swap(&heap[0], &heap[size - 1]);
		heap[size - 1] = 0; size -= 1;
	    for(int i = (size>>1); i >= 0; i--){
	    	heapify(size, i);
	    }
	}
}
int main(){
    int n; scanf("%d", &n);
    for(int i = 0; i < n; i++){
        int t; scanf("%d", &t);
        if(t != 0) push(t);
        else extract();
    }
}

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

문제

문제

출처

ICPC

힙 시간초과

phpmysql 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말