글 읽기 - 안녕하세요 11286 번 질문입니다.

zkfzpf56 3년 전 0

게시판에 있는 반례는 모두 해보았습니다. 다른 반례 부탁드립니다 ㅠㅠ

#include <stdio.h>
int heap[100002] = { 0, };
int heapsize = 0;
int abs(int n) {
	if (n < 0)return -n;
	return n;
}
void insert_heap(int x) {
	heapsize++;
	heap[heapsize] = x;
	int qhsdls = heapsize;
	int parent = qhsdls / 2;
	while (qhsdls != 1 && abs(heap[qhsdls]) <= abs(heap[parent])) {
		int p = 0;
		if (abs(heap[qhsdls] == abs(heap[parent])) && heap[qhsdls] > heap[parent])p = 1;
		if (p == 0) {
			int temp = heap[qhsdls];
			heap[qhsdls] = heap[parent];
			heap[parent] = temp;
		}
		if (abs(heap[parent * 2]) == abs(heap[parent * 2 + 1]) && heap[parent * 2] > heap[parent * 2 + 1]) {
			int temp1 = heap[parent * 2];
			heap[parent * 2] = heap[parent * 2 + 1];
			heap[parent * 2 + 1] = temp1;
		}
		qhsdls = parent;
		parent /= 2;
	}
}
int delete_heap() {
	int item = heap[1];
	heap[1] = heap[heapsize--];
	int qhsdls = 1;
	int child = 2;
	while (qhsdls <= heapsize) {
		if (qhsdls * 2 + 1 <= heapsize && abs(heap[child]) > abs(heap[child + 1]))child++;
		if (child > heapsize || abs(heap[qhsdls]) < abs(heap[child]))break;
		int temp = heap[qhsdls];
		heap[qhsdls] = heap[child];
		heap[child] = temp;
		qhsdls = child;
		child *= 2;
	}
	return item;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int a;
		scanf("%d", &a);
		if (a == 0)
		{
			if (heapsize == 0){
				printf("0\n"); continue;
		}
			printf("%d\n", delete_heap());
		}
		else insert_heap(a);
	}
}

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

문제

문제

출처

ICPC

안녕하세요 11286 번 질문입니다.

zkfzpf56 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말