글 읽기 - 최소힙 문제 오답케이스

unilep 6년 전 2

배열로 구현해보았습니다.

그런데, 여러 케이스를 테스트해봤지만

틀리다고 나와서요

혹시 구현이 잘못되있는 부분이 있을까요?

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, a[100001], t, sz;

void push(int x) {
	a[++sz] = x;
	int t = sz;
	while (t > 1 && a[t] < a[t / 2]) {
		swap(a[t], a[t / 2]);
		t /= 2;
	}
}

int pop() {
	if (sz == 0) return 0;
	int t = a[1];
	a[1] = a[sz];
	a[sz--] = 0;
	int i = 1;
	while(true){
		int idx = -1;
		if (i * 2 + 1 <= sz) {
			if (a[i * 2] < a[i * 2 + 1]) {
				idx = i * 2;
			}
			else {
				idx = i * 2 + 1;
			}
		}
		else if (i * 2 <= sz) {
			idx = i * 2;
		}
		if (idx != -1 && a[i] > a[idx]) {
			swap(a[i], a[idx]);
			i = i * 2;
		}
		else break;
	}
	return t;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> t;
		if (!t) cout << pop() << '\n';
		else push(t);
	}
	
	return 0;
}

dong_s 6년 전 4

31
4
15
11
20
13
19
23
3
24
99
193
1
3
483
213
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

dong_s 6년 전 1

if (idx != -1 && a[i] > a[idx]) {
swap(a[i], a[idx]);
i = idx;
}
else break;

스왑 해주고 i에 idx를 넣어주면 됩니다.

unilep 6년 전 0

이해됬습니다 감사합니다.

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

문제

문제

출처

ICPC

최소힙 문제 오답케이스

unilep 6년 전 2

dong_s 6년 전 4

dong_s 6년 전 1

unilep 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말