このTopCoder probでこのコードが機能するのはなぜですか？

Question

私はこのTopCoderの問題について考えてみることを試みてきましたが、完全に実用的な解決策が出てこないことがありました。

私は、このソリューションが特定のプローブに対してどのように機能するかを把握しようとしていますか？そして、私は元々それを考えていたでしょうか？解決策を読んだ後、私はそれがハフマンコーディングの変種だと考えましたが、それは私が得る限りです。私は本当に魅了よ、この溶液につながると考えていたの何行知っていただきたいと思います..

ここで問題です： http://community.topcoder.com/stat?c=problem_statement&pm=11860&rd=15091

フォックスシエルは宿題がたくさんあります。宿題はいくつかの相互に独立したタスクで構成されています（ ）。別のタスクでは、完了するまでに時間が異なることがあります（ ）。 int [] workCostが与えられます。各iについて、i番目のタスク はworkCost [i]秒かかる。彼女は にパーティーに出席して友達を迎えたいので、できるだけ早くすべての仕事を完了したいと考えています。

主な問題は、シエルを含むすべてのキツネは、宿題を行うことが本当に嫌いです。それぞれのキツネは仕事の1つをして喜んでいます。幸いにも、 22世紀のロボット猫、ドラえもんは、Fox Cielに分割を与えました ハンマー：どんなキツネを2つのキツネに分けることができる魔法のガジェット。

int splitCostが指定されています。キツネのスプリットハンマーを使用すると、瞬時に です。ハンマーがキツネで使用されると、キツネは スプリットに始まります。 splitCost秒後、彼女は2つのキツネ - オリジナルのキツネと別の完全に新しいキツネに変身します。キツネが分裂している間に、 彼女に再びハンマーを使用することは許されません。

タスクの作業を中断することはできません。一度、キツネが作業を開始すると、完了する必要があります。 への複数のキツネが同じタスクで協力することは許されません。彼女はハンマーを使って分割された である間、仕事ではキツネは働くことができません。同じ狐を複数回に分けることも可能です。 彼女は仕事の1つを解決する前と後の両方に狐を分割することが可能です。

フックスがすべてのタスクを解決できる最も短い時間を計算して返します。

そして、ここでは、私はあなたが「最大（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

、最初に見つかったソリューションです。そうでしょう？基本的に、あなたが1つのキツネを持っている場合、あなたは2つに分割し、それぞれのタスクを個別に実行します。このプロセスを「マージ」と呼ぶことにしましょう。

ここで、a> b> cという3つのジョブa、b、cがあるとします。マージ（マージ（a、b）、c）またはマージ（マージ（a、c）、b）またはマージ（merge（b、c）、a）のいずれかができます。数学を行い、あなたはmerge（merge（b、c）、a）がこれら3つの中で最も少ないことを証明することができます。

誘導を使用して、この解決策が（3だけでなく）任意の数のジョブに対して有効であることを証明できるようになりました。

Answer 2

これは土台から木を作り上げています。 最小の2つの要素を削除すると、最小の要素を計算するコストは、次に小さいものと分割のコストよりも常に低くなります。 （これについてのより完全な証拠については、ElKaminaの記事を参照してください）。

したがって、ツリー内に2つの要素（たとえば4と2）があり、分割コストが4だった場合、最小の時間は常に8になります（最小要素の次に分割のコストを加えたもの）。

だから、私たちのツリーを構築するために：我々はworkCost [1,3,4,5,7,8,9,10]、そして私たちのsplitCostだから3

で得たとしましょう、私たちは見て2つの最小要素：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 

あなたは、この木まで後方トレースする場合は、それがどのように見るのは簡単ですS（6）、S（6）、S（10）、S（8）、S（8）はS（11）である。