글 읽기 - c언어로구현했는데 시간초과가뜨네요..

jow1025 4년 전 0

힙의 삽입삭제연산이 NlongN으로알고있는데

어디부분에서 시간초과를 만드는지 알려주시면 감사하겠습니다.

#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;

long long  heap[100001];
long long heap_size = 0;
void delete_heap();
void insert_heap(long long x);
int main()
{
	long long N;
	cin >> N;
	long long x;
	for (int i = 0; i < N; i++)
	{
		cin >> x;
		if (x == 0 && heap_size == 0)
		{
			cout << 0 << '\n';
		}
		else if(x==0)
			delete_heap();
		else
			insert_heap(x);
	}
}
void delete_heap()
{
	
	int parent = 1;
	int child = 2;
	int i;
	long long item = heap[1];
	long long temp = heap[heap_size];
	heap_size--;
	while (child <= heap_size)
	{
		if ((child < heap_size) && (heap[child] < heap[child + 1]))
			child++;
		if (temp >= heap[child])break;
		else
		{
			heap[parent] = heap[child];
			parent = child;
			child = child * 2;
		}
	}	
	heap[parent] = temp;
	cout << item << '\n';

}
void insert_heap(long long x)
{
	 int i;
	heap_size++;
	i = heap_size;
	while ((i != 1) && (x > heap[i/2]))
	{
		heap[i] = heap[i/2];
		i /= 2;
	}
	heap[i] = x;
}

djm03178 4년 전 0

https://www.acmicpc.net/proble...

jow1025 4년 전 0

cout이 느리다고해서 '\n'으로만 바꿔서 코드작성중인데 알려주신 코드를 적용해보겠습니다

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

문제

문제

출처

ICPC

c언어로구현했는데 시간초과가뜨네요..

jow1025 4년 전 0

djm03178 4년 전 0

jow1025 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말