글 읽기 - 반례가 뭘까요..

(追記) (追記ここまで)

반례가 뭘까요..

1655번 - 가운데를 말해요

axtl 1년 전 0

maxheap minheap을 직접 구현해서 실행 해봤습니다.

질문 게시판에 나와있는 반례랑 제가 생각한 데이터들 넣어서 했을 때 문제 없이 정답처럼 나왔는데 제출하면 계속 틀립니다...

반례를 도저히 못찾겠는데 도와주세요...

#include <iostream> 
using namespace std; 
int MaxElement[200001];
int MinElement[200001]; 
void MaxHeapInsert(int num, int count){
 int i = count; 
 while((i > 1) && (MaxElement[i / 2] <= num)){
 MaxElement[i] = MaxElement[i / 2];
 i /= 2; 
 }
 MaxElement[i] = num; 
}
void MinHeapInsert(int num, int count){
 int i = count; 
 while((i > 1) && (MinElement[i / 2] > num)){
 MinElement[i] = MinElement[i / 2];
 i /= 2; 
 }
 MinElement[i] = num; 
}
void reMinHeap(int *element, int count){
 int i = 1; 
 int child = 2; 
 int tmp = element[i];
 while(child <= count){
 if( (child < count - 1) && (element[child] > element[child + 1]) ){
 child++;
 }
 if(tmp < element[child]){
 break;
 }
 element[i] = element[child];
 i = child;
 child *= 2;
 }
 element[i] = tmp; 
}
void reMaxHeap(int *element, int count){
 int i = 1; 
 int child = 2; 
 int tmp = element[i];
 while(child <= count){
 if( (child < count - 1) && (element[child] > element[child + 1]) ){
 child++;
 }
 if(tmp >= element[child]){
 break;
 }
 element[i] = element[child];
 i = child;
 child *= 2;
 }
 element[i] = tmp; 
}
void MaxHeapDelete(int *element, int count){
 element[1] = element[count]; 
 reMaxHeap(element, count - 1); 
}
void MinHeapDelete(int *element, int count){
 element[1] = element[count]; 
 reMinHeap(element, count - 1); 
}
int main(){
 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 int cnt = 1;
 int N;
 cin >> N; 
 for(int i = 0; i < N; i++){
 int a; 
 cin >> a; 
 if(cnt == 1){
 MaxHeapInsert(a, (cnt / 2) + 1); 
 }
 else if(cnt % 2 == 0){
 if(a > MaxElement[1]){
 MinHeapInsert(a, cnt / 2); 
 }
 else{
 MinHeapInsert(MaxElement[1], cnt / 2); 
 MaxHeapDelete(MaxElement, cnt / 2); 
 MaxHeapInsert(a, cnt / 2); 
 }
 }
 else{
 if(a < MinElement[1]){
 MaxHeapInsert(a, (cnt + 1) / 2); 
 }
 else{
 MaxHeapInsert(MinElement[1], (cnt + 1) / 2); 
 MinHeapDelete(MinElement, cnt / 2); 
 MinHeapInsert(a, cnt / 2); 
 }
 }
 cnt += 1; 
 cout << MaxElement[1] << "\n"; 
 }
 return 0; 
}

hokerz7 1년 전 2

반례 들고 왔습니다.

12
6 6 6 5 5 5 6 6 6 5 5 5
output
6
6
6
6
6
5
6
6
6
5 << 틀린 답
5 << 틀린 답
5
answer
6
6
6
6
6
5
6
6
6
6 
6 
5

axtl 1년 전 1

@hokerz7

감사합니다 ᅲᅲᅲ 덕분에 해결했습니다 감사합니다 ᅲᅲᅲ

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC