java - 为什么此代码适用于此 TopCoder 概率？

Question

自 HOURS 以来，我一直在努力思考这个 TopCoder 问题，但无法找到一个完美的解决方案，并找到了下面给出的一个使用得非常漂亮的解决方案!

我想弄清楚这个解决方案如何适用于给定的问题？而我当初怎么会想到呢？阅读解决方案后，我认为它是霍夫曼编码的一种变体，但这是我所能得到的。我真的很着迷，想知道什么样的思路可以导致这个解决方案..

问题来了: http://community.topcoder.com/stat?c=problem_statement&pm=11860&rd=15091

Fox Ciel has lots of homework to do. The homework consists of some mutually independent tasks. Different tasks may take different amounts of time to complete. You are given a int[] workCost. For each i, the i-th task takes workCost[i] seconds to complete. She would like to attend a party and meet her friends, thus she wants to finish all tasks as quickly as possible.

The main problem is that all foxes, including Ciel, really hate doing homework. Each fox is only willing to do one of the tasks. Luckily, Doraemon, a robotic cat from the 22nd century, gave Fox Ciel a split hammer: a magic gadget which can split any fox into two foxes.

You are given an int splitCost. Using the split hammer on a fox is instantaneous. Once a hammer is used on a fox, the fox starts to split. After splitCost seconds she will turn into two foxes -- the original fox and another completely new fox. While a fox is splitting, it is not allowed to use the hammer on her again.

The work on a task cannot be interrupted: once a fox starts working on a task, she must finish it. It is not allowed for multiple foxes to cooperate on the same task. A fox cannot work on a task while she is being split using the hammer. It is possible to split the same fox multiple times. It is possible to split a fox both before and after she solves one of the tasks.

Compute and return the smallest amount of time in which the foxes can solve all the tasks.

这是我在 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

首先，您确实了解“max(i, j) + splitCost”背后的推理。不是吗？基本上，如果您有一只狐狸，您可以将它分成两只，并独立执行每项任务。我们称此过程为“合并”。

现在假设我们有三个工作 a、b 和 c，使得 a>b>c。您可以执行 merge(merge(a,b),c) 或 merge(merge(a,c),b) 或 merge(merge(b,c),a)。计算一下，你可以证明 merge(merge(b,c),a) 在这三个中是最小的。

您现在可以使用归纳法证明此解决方案对任意数量的作业(不仅仅是 3 个)都有效。