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)をＮ回繰り返しているので、計算量は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();
	}
}