ACM-貪欲入門:POJ 3253 Fence Repair

ACM-貪欲入門:POJ 3253 Fence Repair

中国語題意

入力

出力

例入力

例出力

解決構想

ACコード

文章を簡略化するために、原題は直接原題リンクを見てください.
中国語の題意
長さLの長い板をいくつかの指定された大きさの板に切断することを要求します.大きさはそれぞれa,b,c,d...Lはちょうどa+b+c+d+...、切断するたびに、現在切断操作を実行している板の長さになります.例えば、長さPの板をKとHに切断すると、費用はPとなる.最小の費用の切断方法の必要な費用を求めます.
入力
1行目に整数Nを与え、Nは切断後の板の個数の2~N+1行目を表し、各行に1つの整数を与え、1枚の切断後の板の長さを表す.
しゅつりょく
整数Kを含む行を出力し、Kは問題の意味に必要な結果を表す.
サンプル入力
3 8 5 8
サンプル出力
34
解決策
サンプル入出力の結果34は、21を13および8に切断し、21を費やす.長さ13の板を8と5に切断し、13を費やす.全部で21+13=34かかります.「二叉木」の形で、カットごとに見られます.分割を行う板の長さをA[i]とし、分割後の板の長さをそれぞれA[2*i]とし、A[2*i+1]にはA[i]=A[2*i]+A[2*i+1]があることを少し考えてみると、かかる費用が非葉接点であることが分かる重み値の総和・再観察を経て、全ての「葉接点の重み値にその経路を乗じた」総和がかかる費用であることが、上記の特徴による、ハフマンの木を連想するのは難しくない.

N枚の板の長さをN本の木に初期化し、この木(1つの接点のみ)の重み値は対応する板の長さである.

貪欲アルゴリズムを用いて,重み値が最も小さい2つの木を左右の子供の接点(すなわち板)として選択するたびに新しい木を生成し,元の2つの木を削除し,新しい木の根接点重み値は元の2つの木の重み値の和とする.最後に残った1本の木はハフマンの木で、この木の「費用」(葉の結点の重みにその経路を乗じた)はテーマに求められる.

ハフマンツリーについて知らない学生は自分で検索してください.理解してください.ここでは詳しく説明しません.
ACコード

#include
#include
using namespace std;
typedef long long ll;
//maxn        ，       
const ll maxn = 1000000009;
//  
struct Node{
	ll sum;//         
	ll basic;//          
};
//        
bool operator<(const Node &a,const Node &tmp){
		return a.basic<tmp.basic;
}
//    
priority_queue<Node> q;
//          ，             “   ”    
inline void re(Node &tmp){
	//maxn      
	tmp.basic=maxn-tmp.basic;
}
int main(){
	ll n,tmp;
	//     （       ） 
	Node work;
	Node work2;
	work.sum = 0;
	scanf("%lld",&n);
	for(ll i = 0;i<n;++i){
		scanf("%lld",&tmp);
		work.basic = tmp;
		//  ，      
		re(work);
		q.push(work);
	}
	
	while(q.size()!=1){
		work = q.top();q.pop();
		work2 = q.top();q.pop();
		//  ，     
		re(work);
		re(work2);
		//           
		work.basic+=work2.basic;
		//      
		work.sum+=work2.sum;
		work.sum+=work.basic;
		//  ，         
		re(work);
		q.push(work);
	}
	printf("%lld
",q.top().sum);
	return 0;
}