이 TopCoder prob에서이 코드가 작동하는 이유는 무엇입니까?

Question

저는이 TopCoder 문제에 대해 생각 해본 결과 완벽하게 작동하는 해결책을 찾을 수 없었습니다. 그리고 아래에 주어진 내용이 미적 아름답게 사용 된 것을 발견했습니다!

이 솔루션이 주어진 probem에 대해 어떻게 작동하는지 파악하려고합니다. 그리고 어떻게 내가 원래 그것을 생각할 수 있었 을까? 솔루션을 읽은 후에는 허프만 코딩의 변형이라고 생각했지만 최대한 멀리 할 수있었습니다. 나는

다음은 문제입니다 .. 정말 매혹있어이 솔루션으로 이어질 수 있다고 생각 어떤 줄 알고 싶습니다 : http://community.topcoder.com/stat?c=problem_statement&pm=11860&rd=15091

폭스 시엘은 할 숙제가 많이 있습니다. 숙제는 서로간에 독립적 인 작업으로 이루어져 있습니다 ( ). 다른 작업을 완료하려면 시간이 다를 수 있습니다 ( ). int [] workCost가 주어집니다. 각 i에 대해 i- 번째 작업을 완료하려면 workCost [i] 초가 걸립니다. 그녀는 파티에 참석하고 친구들을 만나고 싶으므로 최대한 빨리 개의 작업을 모두 끝내기를 원합니다.

Ciel을 비롯한 모든 여우가 숙제를하는 것이 정말 싫습니다. 각 여우는 그 일 중 하나만 기꺼이 수행합니다. 다행히도, 22 세기의 로봇 고양이 도라에몽은 폭스 시엘 (Fox Ciel)에게 균열을주었습니다 망치 : 여우를 두 마리의 여우로 나눌 수있는 마법의 도구.

int splitCost가 제공됩니다. 폭스에 망치를 사용하면 순간적입니다. 일단 망치가 여우에 사용되면, 여우는 균열이 으로 시작됩니다. splitCost 초 후에 그녀는 두 여우로 변합니다 - 원래 여우와 또 다른 완전히 새로운 여우. 여우가 갈라지는 동안 그녀에게 다시 망치를 사용하는 것은 허용되지 않습니다.

작업에 대한 작업을 중단 할 수 없습니다. 여우가 작업을 시작하면 작업을 완료해야합니다. 에 대한 여러 여우가 동일한 작업에 협조하는 것은 허용되지 않습니다. 그녀가 망치를 사용하여 쪼개는 인 동안 여우는 작업에서 작동 할 수 없습니다. 동일한 여우 을 여러 번 나눌 수 있습니다. 그녀가 작업 중 하나를 해결하기 전후에 여우를 나눌 수 있습니다.

여우가 으로 모든 작업을 해결할 수있는 최소 시간을 계산하여 반환하십시오. 여기

그리고

난 당신이`최대 (I, J) + splitCost '뒤에 추론을 실현하는 모든 일이 link

import java.util.*; 

public class FoxAndDoraemon { 
    public int minTime(int[] workCost, int splitCost) { 
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); 

    for(int i : workCost) pq.offer(i); 

    while(pq.size()>=2) { 
     int i = pq.poll(); 
     int j = pq.poll(); 
     pq.offer(Math.max(i, j) + splitCost); 
    } 
    return pq.poll(); 

    } 
} 

Answer 1

우선에서 발견 된 솔루션입니다. 그렇지? 기본적으로 여우가 하나있는 경우 두 개로 나누고 각각의 작업을 독립적으로 수행합니다. 이 프로세스를 "병합"이라고합니다.

이제 a> b> c와 같은 세 가지 작업 a, b 및 c가 있다고 가정합니다. 병합 (병합 (a, b), c) 또는 병합 (병합 (a, c), b) 또는 병합 (병합 (b, c), a)을 수행 할 수 있습니다. 수학을 수행하면 merge (merge (b, c), a)가이 세 가지 중에서 가장 적음을 증명할 수 있습니다.

유도를 사용하여이 솔루션이 모든 작업 (3 개가 아님)에 유효 함을 증명할 수 있습니다.

Answer 2

처음부터 나무를 만들고 있습니다.

알고리즘은 하나의 기본 사실을 사용하여 작업합니다. 두 개의 가장 작은 요소를 제거하면 가장 작은 요소를 계산하는 비용이 항상 다음으로 작은 스플릿과 비용의 비용보다 적습니다. (이에 대한 훨씬 더 철저한 증거는 ElKamina의 글을 참고하십시오).

그래서 트리에 두 개의 요소 (예 : 4와 2)가 있고 분할 비용이 4 인 경우 가장 적은 시간이 항상 8이됩니다 (가장 작은 요소 다음에 분할 비용을 더한 금액).

그래서, 우리의 트리를 구축 :의 우리가 workCost [1,3,4,5,7,8,9,10, 우리 splitCost 그래서 3

입니다있어 가정 해 봅시다, 우리는보고 두 가지 가장 작은 요소 : 1,3 이러한 계산을위한 '비용'은 최소 6 개입니다 (가장 큰 숫자와 분할 비용을 더한 다음 6을 대기열에 다시 넣으면 본질적으로 하위 트리가 추가됩니다) :

6 
1 3 

여기서 '높이'/ '비용'은 총 6 개입니다. 이 과정을 반복하면 가장 작은 하위 요소 (기존 하위 트리 또는 완료되지 않은 새 숙제)를 사용하여 트리를 작성합니다.

결국 같이 표시됩니다 솔루션 :이 나무까지 거꾸로 추적 경우

    S(17) 
      S(13)  S(14) 
     S(10)  9 10  S(11) 
    S(6)  7   S(8)  8 
1  3     4 5 

(S (X)는 분할 비용을 더한 해결 아래 모든 인 경우),이 방법을 쉽게 알 수 수식은 그것을 해결했다 : 1과 3의 비용은 S (6), 4와 5는 S (8), S (6)와 S는 S (10), 8과 S (8)은 S