我想弄清楚这个解决方案如何适用于给定的探测器？我怎么能原先想到它？在阅读完解决方案之后,我认为它是霍夫曼编码的一种变体,但这是我能得到的.我真的很着迷,想知道什么样的思路可以导致这个解决方案..

这是问题所在：@H_301_5@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@H_301_5@ mutually independent tasks. Different tasks may take different amounts@H_301_5@ of time to complete. You are given a int[] workCost. For each i,the@H_301_5@ i-th task takes workCost[i] seconds to complete. She would like to@H_301_5@ attend a party and meet her friends,thus she wants to finish all@H_301_5@ tasks as quickly as possible.

The main problem is that all foxes,including Ciel,really hate doing@H_301_5@ homework. Each fox is only willing to do one of the tasks. Luckily,@H_301_5@ Doraemon,a robotic cat from the 22nd century,gave Fox Ciel a split@H_301_5@ 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@H_301_5@ instantaneous. Once a hammer is used on a fox,the fox starts to@H_301_5@ split. After splitCost seconds she will turn into two foxes — the@H_301_5@ original fox and another completely new fox. While a fox is splitting,@H_301_5@ 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@H_301_5@ a task,she must finish it. It is not allowed for multiple foxes to@H_301_5@ cooperate on the same task. A fox cannot work on a task while she is@H_301_5@ being split using the hammer. It is possible to split the same fox@H_301_5@ multiple times. It is possible to split a fox both before and after@H_301_5@ she solves one of the tasks.

Compute and return the smallest amount of time in which the foxes can@H_301_5@ 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(); 

  } 
}