글 읽기 - c++ 반례구합니다!(c++)

112224 5년 전 0

테스트케이스의 갯수가 주어지지 않아

반복조건을 x에 숫자가 들어왔을 때로 잡았습니다.

이후엔 이분탐색으로 문제를 풀었는데 틀렸습니다가 나오네요 ㅠㅠ

반례와 혹시 개선이 필요한 부분알려주시면 감사하겠습니다.

#include<iostream>
#include<algorithm>
using namespace std;

int a[1000001];
int main()
{
    int x;
    while(scanf("%d",&x)==1)
    {
        x*=10000000;
        int n;
        scanf("%d",&n);
        
        for(int i=0;i<n;i++)
        {
            scanf("%d",a+i);
        }
        
        sort(a,a+n);            //크기순으로 sort
        bool flag=false;        // 처음 나오는 답이 abs(t1-t2)가 가장 큼
        for(int i=0;i<n/2;i++)  // i<n 까지로 변경 후에도 틀림
        {
            int t=x-a[i];
            if(t>a[n-1])        //danger가 가장 계산이 많을 것 같아 빨리 거르기 위함.
            continue;
            int l=i,h=n;        // i 이전은 범위에서 제외
            int ans;
            while(l<=h)        //이분탐색 시작
            {
                int m=(l+h)/2;
                if(a[m]<t)
                l=m+1;
                else if(a[m]>t)
                h=m-1;
                else
                {
                    ans=m;
                    flag=true;
                    break;
                }
                
            }
            if(flag)
            {
                printf("yes %d %d\n",a[i],a[ans]);
                break;
            }
            
        }
        if(!flag)
        printf("danger\n");
    }
}

112224 5년 전 0

하나 넣었을 때 정답으로 출력하는 에러가 있었네요 ㅠ

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

문제

문제

출처

ICPC

c++ 반례구합니다!(c++)

112224 5년 전 0

112224 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말