読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Fence Repair(PKU No.3253)

Fence Repair(PKU No.3253)

長さL_1, L_2, \dots L_Nの板を長さ\Sigma_{i=1}^N L_iの板から切り出す。板を切断するとき、その板の長さの分だけコストがかかる。例えば、長さ21の板から長さ5,8,8の3つの板を切り出すとき、21の板を長さ13と8の板に切断すると21のコストがかかり、13の板をさらに5と8の板に切断するとコストが13かかる。合計コストは34となる。N,L_1, L_2, \dots L_Nが与えられたとき、最小のコストを求める。
制約
1 \leq N \leq 20,000
1 \leq L_i \leq 50,000

アルゴリズム

最初の板からトップダウンに長さL_1, L_2, \dots L_Nの板に分割しようと考えると難しい。長さL_1, L_2, \dots L_Nの板からボトムアップにマージしていくと考えれば分かりやすい(マージコスト=分割コスト)。小さい順にマージしていく貪欲法。これはハフマン木を作るアルゴリズムに他ならない。合計コストは、intの範囲に納まらないことに注意しなければならない。PriorityQueueを用いて実装するのがやり易い。ヒープ操作O(N)をN回繰り返しているので、計算量はO(Nlog N)。

コード

import java.util.*;
//import java.math.*;
public class pku3253 {
	static Scanner scanner;
	pku3253(){
		int N = scanner.nextInt();
		PriorityQueue<Integer> q = new PriorityQueue<Integer>(N);
		for(int i=0; i<N; i++) q.offer( scanner.nextInt() );
		System.out.println( solve(N,q) );
	}
	long solve(int N, PriorityQueue<Integer> q){
		long ans = 0;
		while( q.size() > 1 ){
			int L = q.poll()+q.poll();
			q.offer( L );
			ans += (long)L;
		}
		return ans;
	}
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new pku3253();
	}
}