글 읽기 - 세용액 예외질문입니다.

klize 6년 전 0

대칭으로 들어오는거, 한종류만 들어오는거 다해봤는데도 안되네요..

방법은 L[i]+L[j] 의 반대부호로 i<k<j 조건으로 L[i]+L[k]+L[j] 의 절대값이 0에 가깝게 되는 k 찾아가는건데..

시간은 i+1<j 조건으로 n 시간에 탐색하면서

Binary Search도 (i,j)구간이 줄어들어서 길어야 총 n번 탐색에 한 iteration당 lg n이라 총 n lg n 이라고 생각하고있는데...

일단 12%진행하다 바로 틀려버려서.. 예외가 어떤게 있을지 궁금합니다.

def bs(t,s,e,L):
    while(s<=e):
        mi=(s+e)//2
        if t==L[mi]:
            return mi
        elif t<L[mi]:
            e=mi-1
        elif t>L[mi]:
            s=mi+1
        
    if e<0:
        return 0
    elif s>len(L)-1:
        return len(L)-1
    else:
        a,b=abs(t-L[s]),abs(t-L[e])
        if a<=b:
            return s
        else:
            return e

N=input()
L=sorted(map(int,raw_input().split()))
#print L
i,j=0,N-1
r=[L[i],L[1],L[j]]
while i+1<j:
    ts=L[i]+L[j]
    k=bs(-ts,i,j,L)
    if k<=i:
        k=i+1
    elif k>=j:
        k=j-1
    #print L[i],L[k],L[j]
    s=L[i]+L[k]+L[j]
    if abs(s) < abs(sum(r)):
        r=[L[i],L[k],L[j]]
    i+=(ts<0)
    j-=(ts>=0)

    #print r
#print r
print r[0],r[1],r[2]

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

문제

문제

출처

ICPC

세용액 예외질문입니다.

klize 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말