忍者ブログ
[PR]
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。



2017/04/30 17:58 |
柵を修理
http://qiita.com/ukisoft/items/1600072d32ca199b0694
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


2015/01/09 22:56 | Comments(0) | PHP

コメント

コメントを投稿する






Vodafone絵文字 i-mode絵文字 Ezweb絵文字 (絵文字)



<<「第27回オフラインリアルタイムどう書くの参考問題」をPHPで解く | HOME | 「ミスPSコンテスト2014」結果発表>>
忍者ブログ[PR]