6

从 HOURS 开始，我一直在尝试思考这个 TopCoder 问题，但无法提供完美的解决方案，并发现下面给出的解决方案使用得非常漂亮！

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

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

Fox Ciel 有很多功课要做。作业由一些相互独立的任务组成。不同的任务可能需要不同的时间来完成。您将获得一个 int[] workCost。对于每个 i，第 i 个任务需要 workCost[i] 秒才能完成。她想参加一个聚会和认识她的朋友，因此她想尽快完成所有任务。

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

你得到一个 int splitCost。在狐狸身上使用劈锤是瞬间的。一旦在狐狸身上使用锤子，狐狸就会开始分裂。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(); 

  } 
}
4

2 回答 2

6

首先，您确实意识到“max(i, j) + splitCost”背后的原因。不是吗？基本上，如果您有一只狐狸，您可以将其分成两部分并独立执行每项任务。让我们称这个过程为“合并”。

现在假设我们有三个工作 a、b 和 c，使得 a>b>c。您可以执行合并（合并（a，b），c）或合并（合并（a，c），b）或合并（合并（b，c），a）。做数学，你可以证明 merge(merge(b,c),a) 在这三个中最少。

您现在可以使用归纳法来证明此解决方案适用于任意数量的工作（不仅仅是 3 个）。

于 2012-04-27T18:47:22.713 回答
3

它正在从头开始建造一棵树。

该算法使用一个基本事实来工作：如果删除两个最小元素，则计算最小元素的成本始终小于下一个最小元素的成本加上拆分。（请参阅 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(X) 是拆分成本加上解决它下面的所有问题）

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

如果你向后追溯这棵树，很容易看出公式是如何解决它的：1 和 3 的成本是 S(6)，4 和 5 是 S(8)，然后 S(6) 和 7 是 S(10) ), 8 和 S(8) 是 S(11) 等。

于 2012-04-27T19:11:12.393 回答