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

wanderkind 1년 전 0

저만 어렵게 풀고 있는 건가 싶은데 반례가 도대체 뭘까 궁금합니다.

c,b=map(int,input().split())
p=sorted([*map(int,input().split())]) 
q=sorted([*map(int,input().split())]) # 두 수열 오름차순 정렬
M=max(p)+1
l,r=0,b
y=-1
try:
    # 이분탐색으로 지불하려는 비용 중 상품의 만족도의 최대값보다 큰 값의 인덱스 찾기
    while 1:
        t=(l+r)//2
        z=q[t]
        if y==z:
            break
        else:
            y=z
        if z>M:
            r=t
        elif M>z:
            l=t
        else:
            break
    while q[t]==M:
        t-=1
    v=q[0:t+1] # 지불하려는 비용 중 상품의 만족도의 최대값보다 큰 값을 제거
    # 상품과 고객 수가 같도록 둘 중 긴 쪽을 잘라냄
    # (지불 비용은 가장 작은 값부터, 상품 만족도는 가장 큰 값부터)
    d=len(v)
    if c>d:
        A=p[-d:]
        B=v
    elif c<d:
        A=p
        B=v[:c-d]
    else:
        A,B=p,v
    u=len(A)
    # 상품 만족도는 큰 값부터, 지불 비용은 작은 값부터 매칭하여 그 차를 더함,
    # 합이 최고가 될 때 출력함
    W=0
    i=-1
    while i<u-1:
        i+=1
        Y=A[u-i-1]-B[i]
        if Y<0:
            break
        else:
            W+=Y
    print(W)
except IndexError:
    print(0)

methe12345 1년 전 0

주석이 없으셔서.. 코드 읽기가 좀 불편합니다. ㅠㅠㅠ

wanderkind 1년 전 0

@methe12345 주석 달았습니다. 지적해주셔서 감사합니다.

methe12345 1년 전 0

input

5 5

42 59 60 64 67

13 17 29 29 33

ans: 171

output: 162

methe12345 1년 전 0

AC 코드랑 같이 random 함수로 돌려본거라 숫자는 좀 난잡합니다..

methe12345 1년 전 0

5 5

6 7 8 9 10

1 2 3 3 4

도 있겠네요

ans: 27

output: 25

wanderkind 1년 전 0

@methe12345 감사합니다.

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

문제

문제

출처

ICPC

반례가 뭘까요??

wanderkind 1년 전 0

methe12345 1년 전 0

wanderkind 1년 전 0

methe12345 1년 전 0

methe12345 1년 전 0

methe12345 1년 전 0

wanderkind 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말