http://qiita.com/ukisoft/items/1600072d32ca199b0694
Fence Repair
PHP5.3で優先度つきキューが実装されています。
Fence Repair
PHP5.3で優先度つきキューが実装されています。
<?php
class FenceRepair{
public static function calc(array $boards){
if(count($boards) < 1){ return false; }
if(count($boards) < 2){ return current($boards); }
$cost = 0;
// キューに突っ込む
$queue = new SplPriorityQueue();
foreach($boards as $val){
// 取り出しは降順なので、昇順にするためにマイナス
$queue->insert($val, -$val);
}
while(true){
// 短い2本を取り出す
$cost1 = $queue->extract();
$cost2 = $queue->extract();
$costt = $cost1+$cost2;
$cost += $costt;
// キューが無くなったら終了
if($queue->isEmpty()){
return $cost;
}
// くっつけた後の板を挿入
$queue->insert($costt, -$costt);
}
}
}
$totalcost = FenceRepair::calc([1,2,3,4,5]);
とっても簡単にできました。PR