为什么这个代码适用于这个TopCoder问题？

Question

我一直试图从HOURS开始考虑这个TopCoder问题并且无法找到一个完美的解决方案并且发现下面给出的那个疯狂地使用了!

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

这是问题所在:http: //community.topcoder.com/stat？c = proby_statement&pm = 11860&rd = 15091

Fox Ciel有很多功课要做.作业包括一些相互独立的任务.不同的任务可能需要不同的时间来完成.你得到一个int [] workCost.对于每个i,第i个任务需要workCost [i]秒才能完成.她想参加一个派对并与她的朋友见面,因此她希望尽快完成所有任务.

主要问题是包括Ciel在内的所有狐狸都非常讨厌做作业.每只狐狸只愿意做其中一项任务.幸运的是,哆啦A梦,一个来自22世纪的机器猫,给了Fox Ciel一把分裂的锤子:一个可以将任何狐狸分成两只狐狸的神奇小工具.

你得到一个int splitCost.在狐狸上使用分裂锤是瞬间完成的.一旦在狐狸上使用锤子,狐狸开始分裂.在分秒成本后,她将变成两只狐狸 - 原始的狐狸和另一只全新的狐狸.当狐狸分裂时,不允许再次使用锤子.

任务的工作不能被打断:一旦狐狸开始处理任务,她必须完成它.多个狐狸不允许在同一任务上合作.当使用锤子拆分时,狐狸无法完成任务.可以多次分割相同的狐狸.在解决其中一项任务之前和之后,可以将狐狸分开.

计算并返回狐狸可以解决所有任务的最短时间.

这是我在此链接中找到的解决方案

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.您可以合并(合并(a,b),c)或合并(合并(a,c),b)或合并(合并(b,c),a).算一算,你可以证明合并(merge(b,c),a)在这三者中最少.

您现在可以使用归纳来证明此解决方案适用于任意数量的作业(不仅仅是3个).