私はこのTopCoderの問題について何時間も考えようとしてきましたが、完全に機能する解決策を見つけることができず、めちゃくちゃ美しく使用されている以下の解決策を見つけました！
このソリューションが特定のプローブに対してどのように機能するかを理解しようとしていますか？そして、私は最初にそれをどのように考えることができましたか？解決策を読んだ後、私はそれがハフマンコーディングの変形であると思いましたが、それは私が得ることができる限りです。私は本当に夢中になっていて、どのような考え方がこの解決策につながるのか知りたいです。
問題は次のとおりです： http ：//community.topcoder.com/stat？c = problem_statement＆pm = 11860＆rd = 15091
FoxCielにはやるべき宿題がたくさんあります。宿題は、いくつかの相互に独立したタスクで構成されています。タスクが異なれば、完了するまでに時間がかかる場合があります。int[]workCostが与えられます。iごとに、i番目のタスクが完了するまでにworkCost[i]秒かかります。彼女はパーティーに参加して友達に会いたいので、すべてのタスクをできるだけ早く終えたいと思っています。
主な問題は、シエルを含むすべてのキツネが宿題をするのを本当に嫌うということです。各キツネは、タスクの1つだけを喜んで実行します。幸いなことに、22世紀のロボット猫であるドラえもんは、フォックスシエルにスプリットハンマーを与えました。これは、任意のキツネを2つのキツネに分割できる魔法のガジェットです。
intsplitCostが与えられます。キツネにスプリットハンマーを使用するのは瞬時です。キツネにハンマーを使うと、キツネは裂け始めます。splitCost秒後、彼女は2つのキツネに変わります-元のキツネともう1つの完全に新しいキツネです。キツネが分裂している間、キツネにハンマーを再び使用することは許可されていません。
タスクの作業を中断することはできません。キツネがタスクの作業を開始したら、それを終了する必要があります。複数のキツネが同じタスクで協力することは許可されていません。キツネはハンマーを使って分割されている間はタスクに取り組むことができません。同じキツネを複数回分割することが可能です。彼女がタスクの1つを解決する前と後の両方でキツネを分割することが可能です。
キツネがすべてのタスクを解決できる最小時間を計算して返します。
そして、これが私がこのリンクで見つけた解決策です
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();
}
}