글 읽기 - 뭐가 문제일까요

ae878 4년 전 0

질문에 나와있는 케이스들은 다해봤는데 뭐가 문제인지 자꾸 틀렸습니다가 뜨네요.

#include <stdio.h>

int lastnode = 0;
long long int N;
long long int heap[1000010];
long long int card[200001];

int insert(long long int d) {
	if (lastnode >= 1000010) {
		return 0;
	}

	lastnode++;
	heap[lastnode] = d;

	int child = lastnode;
	int parent = lastnode / 2;

	while (parent > 0) {
		if (heap[parent] > heap[child]) {
			int temp = heap[parent];
			heap[parent] = heap[child];
			heap[child] = temp;
		}
		else {
			break;
		}
	}
	return 1;
}

int pop(long long int *d) {

	if (lastnode == 0) {
		return 0;
	}
	*d = heap[1];

	
	heap[1] = heap[lastnode--];

	int parent = 1;
	int child;
	int left = parent * 2;
	int right = parent * 2 + 1;

	while (left <= lastnode) {
		if (left == lastnode || heap[left] < heap[right]) {
			child = left;
		}
		else {
			child = right;
		}

		if (heap[parent] > heap[child]) {
			long long int temp = heap[parent];
			heap[parent] = heap[child];
			heap[child] = temp;
			parent = child;
			left = parent * 2;
			right = left + 1;
		}
		else {
			break;
		}
	}

	return 1;
}

int main() {
	int N;

	scanf("%d", &N);




	for (int i = 0; i < N; i++) {
		scanf("%lld", &card[i]);
		insert(card[i]);
	}

	long long int card_num1, card_num2;
	pop(&card_num1);
	pop(&card_num2);

	insert(card_num1 + card_num2);

	long long int result = card_num1 + card_num2;



	if (N == 1) {
		printf("0\n");
		return 0;
	}
	else {
		while (true) {
			if (pop(&card_num1) == 0 || pop(&card_num2) == 0) {
				printf("%lld\n", result);
				return 0;
			}
			else {
				result += card_num1 + card_num2;
				insert(card_num1 + card_num2);
			}
		}

	}

	return 0;
}

holenet 4년 전 4

반례입니다.

10 + 10 = 20
20 + 20 = 40
20 + 20 = 40
40 + 40 = 80

으로 총 180이 답이지만 190으로 출력됩니다.

ae878 4년 전 1

감사합니다 힙 구현이 잘못됐었네요!

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

문제

문제

출처

ICPC

뭐가 문제일까요

ae878 4년 전 0

holenet 4년 전 4

ae878 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말