글 읽기 - 반례를 못찾겠습니다 도와주세요

kimdh2577 6년 전 0

정렬은 그냥 예전에 해본 merge sort 코드 사용했고요

최빈값 찾는 함수가 좀 지저분한데 크게 다른 방법이 생각나지 않아서.....

채점은 한 40퍼 조금 넘어서 틀렸다고합니다.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void mergesort(int *data,int start,int end)
{
    int middle;
    if(end>start)
    {
        middle=(start+end)/2;
        mergesort(data,start,middle);
        mergesort(data,middle+1,end);
        merge(data,start,middle,end);
    }
    return;
}

void merge(int *data,int start, int middle, int end)
{
    int *num=(int*)malloc(sizeof(int)*(end-start+1));
    int i=start,j=middle+1,k=0;
    while(i<=middle&&j<=end)
    {
        if(data[i]<data[j])
            num[k++]=data[i++];
        else
            num[k++]=data[j++];
    }
    while(i<=middle)
        num[k++]=data[i++];
    while(j<=end)
        num[k++]=data[j++];
    k=0;
    for(i=start;i<=end;i++,k++)
        data[i]=num[k];
    free(num);
}

int mostn(int *num,int i,int count,int *most,int *checkin)
{
    int countin=1;
    while(num[i]==num[i+1])
        countin++,i++;
    if(countin==count)
        *checkin+=1;
    else if(countin>count)
    {
        *most=num[i];
        *checkin=1;
        return countin;
    }
    if(*checkin==2)
    {
        *most=num[i];
    }
    return count;
}

int main(void)
{
    int n,i,count=0,most,checkin=1,trial=0;
    long sum=0;
    scanf("%d",&n);
    int *num=(int*)malloc(sizeof(int)*n);
    for(i=0;i<n;i++)
        scanf("%d",num+i);
    mergesort(num,0,n-1);
    for(i=0;i<n;i++)
        sum+=num[i];
    for(i=0;i<n;i++)
        if(num[i]==num[i+1])
            count=mostn(num,i,count,&most,&checkin),trial++;
    if(trial==0)
        most=num[1];
    printf("%d\n%d\n%d\n%d\n",(int)round((sum/(double)n)),num[(n+1)/2-1],most,num[n-1]-num[0]);
    return 0;
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다 도와주세요

kimdh2577 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말