Fence Repair

From

poj 3253

Description

农夫约翰想修复牧场周围的一小部分篱笆。他测量围栏，并发现他需要Ñ（1≤ Ñ ≤20000）厚木板，每一个都具有一些整数长度大号我（1≤ 大号我 ≤50000）单元。然后，他购买了一块足够长的单块长板，足以切入N块木板（即，其长度为长度L i的总和）。FJ忽略了“锯缝”，即锯切时因锯末而损失的额外长度；您也应该忽略它。

FJ遗憾地意识到自己没有切割木头的锯子，于是用长木板将其镶嵌到Farmer Don's Farm上，礼貌地询问他是否可以借用锯子。

壁橱资本家农夫唐（Farmer Don）不借给FJ锯，而是提议就木板中的N -1个切口向农夫约翰收费。切割一块木头的费用恰好等于其长度。切割一块长度为21的木板的成本为21美分。

然后，农夫唐让农夫约翰决定切割木板的顺序和位置。帮助农夫约翰确定他可以用来制作N块木板的最低金额。FJ知道他可以按各种不同的顺序切割木板，这将导致不同的费用，因为最终的中间木板长度不同。

Input

第1行：一个整数N，木板数 第2行至N +1行：每行包含一个整数，描述所需木板的长度

Output

第1行：一个整数：要进行N -1次削减，他必须花费的最低金额

Sample Input

3

8

5

8

Sample Output

34

题目第一眼看上去很难入手，其实是一道奇特的贪心题。

切割的方法可以看成二叉树，每一个叶子节点就对应了切割出的目标木板，叶子节点的深度就对应了得到这块目标所需的切割次数，开销的合计就是每个叶子节点的 木板长度×节点的深度

由此可知，因为木板长度是固定的，所以为了使开销最小，应当使得小长度的木板尽可能节点深，也就是说最短的板与次短的板的节点应当是兄弟节点。这样只需建立优先队列，每次取出最短的2块板合成一块板，直到最后只剩一块板即可。

AC代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
int n;
ll l[20000+10],ans,l1,l2;
int main()
{
	cin>>n;
	priority_queue<ll,vector<ll>,greater<ll> >que;
	for(int i=0;i<n;i++)
	{
		cin>>l[i];
		que.push(l[i]);
	}
	while(n>1)
	{
		l1=que.top();
		que.pop();
		l2=que.top();
		que.pop();
		que.push(l1+l2);
		ans+=l1+l2;
		n--;
	}
	cout<<ans<<endl;
}