柵を修理

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本を取り出す
            $costt = $queue->extract() + $queue->extract();
            $cost += $costt;
            // キューが無くなったら終了
            if($queue->isEmpty()){
                return $cost;
            }
            // くっつけた後の板を挿入
            $queue->insert($costt, -$costt);
        }
    }
}

$totalcost = FenceRepair::calc([1,2,3,4,5]);

とっても簡単にできました。