글 읽기 - 왜 틀렸..을까요...

charmant90 8년 전 1

힙을 사용해서 mid 값 기준으로 작은 것은 spq(max_heap), 큰 것은 lpq(min_heap)에 넣고

mid 값을 갱신하는 코드를 만들었습니다.

어떤 케이스가 안되는 건지 도저히 모르겠네요...

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

int a[100000];
int mid;

int main() {
	priority_queue<int, vector<int>, greater<int>> lpq;
	priority_queue<int> spq;
	int n;

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int data;

		scanf("%d", &data);

		if (i == 0) {
			mid = data;
		}
		else {
			if (mid > data) {
				spq.push(data);
			}
			else if (mid < data) {
				lpq.push(data);
			}

			int ssize = spq.size();
			int lsize = lpq.size();

			if ((ssize + lsize + 1) % 2 == 0) {
				if (ssize > lsize) {
					int temp = mid;
					mid = spq.top();
					spq.pop();
					lpq.push(temp);
				}
			}
			else {
				if (ssize > lsize) {
					int temp = mid;
					mid = spq.top();
					spq.pop();
					lpq.push(temp);
				}
				else if (ssize < lsize) {
					int temp = mid;
					mid = lpq.top();
					lpq.pop();
					spq.push(temp);
				}
			}
		}

		printf("%d\n", mid);
	}

	return 0;
}

sang7 8년 전 4

5 4 4 4 3 3

이라는 테스트 케이스를 적용하면 답은

5 4 4 4 4 4 일텐데 5 4 4 4 4 3 이 나오시네요.

mid 값과 같은 값이 들어 왔을 경우 저장을 하지 않는게 문제 같아 보이네요

charmant90 8년 전 0

sang7 감사합니다.

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

문제

문제

출처

ICPC

왜 틀렸..을까요...

charmant90 8년 전 1

sang7 8년 전 4

charmant90 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말