srand   1년 전

초기 단순하게 R로 소팅해서 시도 했다가 WA 나와서 

Hungarian 으로 했는데요, 

greedy로 AC 받으신분들 아래 입력에 대해서 답 나오시나요 ?

IN #1
6
19 1.80
130 1.75
44 1.71
776 1.33
493 1.15
58 1.51

ANS #1
2522.91
        19       34.2      61.56    110.808  [199.454]    359.018
       130    [227.5]    398.125    696.719    1219.26     2133.7
        44      75.24   [128.66]    220.009    376.216    643.329
     [776]    1032.08    1372.67    1825.65    2428.11    3229.39
       493     566.95    651.992    749.791     862.26  [991.599]
        58      87.58    132.246  [199.691]    301.534    455.316

IN #2
4
457 1.71
356 1.57
494 1.45
139 1.93

ANS #2
3039.70
     [457]     781.47    1336.31     2285.1
       356   [558.92]    877.504    1377.68
       494      716.3    1038.63  [1506.02]
       139     268.27  [517.761]    999.279

IN #3
3
467 1.66
997 1.57
282 1.65

ANS #3
2539.96
       467   [775.22]    1286.87
     [997]    1565.29    2457.51
       282      465.3  [767.745]

bupjae   1년 전

이 문제에 제출된 대부분의 "맞았습니다" 를 받은 제출은

매달 "비용 증가량" P*(R-1) 이 가장 클 것으로 예상되는 소프트웨어를 구입하는 greedy 알고리즘을 구현했습니다.

그런데 이렇게 구현하면 제시하신 데이터 #1 및 #2 에서 최적해가 도출되지 않는 것을 확인했습니다.

.

데이터 #1 및 #2 를 "데이터 추가해 주세요" 라고 요청글을 쓰면 됩니다.

저격 제출은 95248543 라고 하시면 됩니다. 방금 설명한 greedy 방식으로 구현해서 최적해가 아닌 답을 도출하는 프로그램입니다.

.

이 문제는 단순 greedy 로는 풀기 어려운 문제로 보입니다.

제시하신 헝가리안을 정해로 삼고 문제의 난이도를 올리는게 맞는 것으로 보입니다.

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