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