글 읽기 - 반례가있을까요??

twl0812 1년 전 0

질문게시판에 나온반례전부를 해봤는데 잘나옵니다.하지만 틀렸다고 나옵니다.

반례좀 부탁드려요 ㅠㅠ

maxheap-> 중간값보다 큰값을모아놓는 최소힙

minheap -> 중간값 이하의 값을 모아놓는 최대힙

#include<stdio.h>
#include<stdlib.h>
#define MAX 50001
int minheap[MAX];
int maxheap[MAX];
int minsz=0;
int maxsz=0;
void minEnqueue(int v)
{
    if(minsz==MAX-1)
    {
        return;
    }
    minsz++;
    minheap[minsz]=v;
    int me=minsz;
    int parent=me/2;
    while(1)
    {
        if(me==1)
        {
            return;
        }
        if(minheap[parent]>=minheap[me])
        {
            return;
        }
        else
        {
            int temp=minheap[me];
            minheap[me]=minheap[parent];
            minheap[parent]=temp;
            me=parent;
            parent=me/2;
        }
    }
}
void maxEnqueue(int v)
{
    if(maxsz==MAX-1)
    {
        return;
    }
    maxsz++;
    maxheap[maxsz]=v;
    int me=maxsz;
    int parent=me/2;
    while(1)
    {
        if(me==1)
        {
            return;
        }
        if(maxheap[parent]<=maxheap[me])
        {
            return;
        }
        else
        {
            int temp=maxheap[me];
            maxheap[me]=maxheap[parent];
            maxheap[parent]=temp;
            me=parent;
            parent=me/2;
        }
    }
}
int findrep(int me)
{
    int l=me*2;
    int r=l+1;
    if(l>minsz)
    {
        return 0;
    }
    else if(r>minsz)
    {
        return l;
    }
    else if(minheap[l]<minheap[r])
    {
        return r;
    }
    else return l;
}
int mindequeue(void)
{
    if(minsz==0)
    {
        return -999;
    }
    int res=minheap[1];
    minheap[1]=minheap[minsz];
    minsz--;
    int me=1;
    int rep=findrep(me);
    while(1)
    {
        if(rep==0)
        {
            return res;
        }
        if(minheap[me]>=minheap[rep])
        {
            return res;
        }
        else
        {
            int temp=minheap[rep];
            minheap[rep]=minheap[me];
            minheap[me]=temp;
            me=rep;
            rep=findrep(me);
        }
    }
}
int findrep2(int me)
{
    int l=me*2;
    int r=l+1;
    if(l>maxsz)
    {
        return 0;
    }
    else if(r>maxsz)
    {
        return l;
    }
    else if(maxheap[l]>=maxheap[r])
    {
        return r;
    }
    else return l;
}
int maxdequeue(void)
{
    if(maxsz==0)
    {
        return -999;
    }
    int res=maxheap[1];
    maxheap[1]=maxheap[maxsz];
    maxsz--;
    int me=1;
    int rep=findrep2(me);
    while(1)
    {
        if(rep==0)
        {
            return res;
        }
        if(maxheap[me]<=maxheap[rep])
        {
            return res;
        }
        else
        {
            int temp=maxheap[rep];
            maxheap[rep]=maxheap[me];
            maxheap[me]=temp;
            me=rep;
            rep=findrep2(me);
        }
    }
}
int main()
{
    int a;
        scanf("%d",&a);
        for(int i=0;i<a;i++)
        {
            int b;
            scanf("%d",&b);
            if(minsz==0) minEnqueue(b); //minheap empty
            else if(b>minheap[1] && maxsz==0) maxEnqueue(b); // maxheap empty;
            else if(b<=minheap[1]) minEnqueue(b); //b==low
            else if(b>minheap[1] && b<=maxheap[1]) minEnqueue(b); //b==mid
            else if(b>=maxheap[1]) maxEnqueue(b); //b==high
            if(maxsz>minsz)
            {
                int tmp=maxdequeue();
                minEnqueue(tmp);
            }
            if(minsz-maxsz>1)
            {
                int tmp=mindequeue();
                maxEnqueue(tmp);
            }
            printf("%d\n",minheap[1]);
        }
}

twl0812 1년 전 0

배열크기만 바꾸니까 해결되었습니다.

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

문제

문제

출처

ICPC

반례가있을까요??

twl0812 1년 전 0

twl0812 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말