POJ---3253 Fence Repair

POJ—3253 Fence Repair

Description

Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the “kerf”, the extra length lost to sawdust when a sawcut is made; you should ignore it, too.

FJ sadly realizes that he doesn’t own a saw with which to cut the wood, so he mosies over to Farmer Don’s Farm with this long board and politely asks if he may borrow a saw.

Farmer Don, a closet capitalist, doesn’t lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.

Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.

Input

Line 1: One integer N, the number of planks

Lines 2…N+1: Each line contains a single integer describing the length of a needed plank

Output

Line 1: One integer: the minimum amount of money he must spend to make N-1 cuts

Sample Input

3

8

5

8

Sample Output

34

Hint

He wants to cut a board of length 21 into pieces of lengths 8, 5, and 8.

The original board measures 8+5+8=21. The first cut will cost 21, and should be used to cut the board into pieces measuring 13 and 8. The second cut will cost 13, and should be used to cut the 13 into 8 and 5. This would cost 21+13=34. If the 21 was cut into 16 and 5 instead, the second cut would cost 16 for a total of 37 (which is more than 34).

中文翻译

题目描述

农夫约翰想修修牧场周围的一小部分篱笆。他测量围栏发现他需要N块（1≤ N ≤20000）木板，每一个都具有整数长度Li（1≤ Li≤50000）。然后，他购买了一块足够长的单板长板，以便得到N块木板（即长度为长度L i的总和）。约翰忽略了“切口”，当切割锯切时，木屑损失了额外的长度，你也应该忽略它。

约翰遗憾地意识到他没有切割木头的锯子，所以他去农夫唐的农场，礼貌地问他是否可以借锯。唐并没有借给约翰锯，而是向约翰提供了切割N -1块每块的切割费用。切割一块木头的费用与其长度完全相同。切割长度为21的木板需要21美分。

唐让约翰决定切割木板的顺序和位置。帮助约翰确定他得到N个木板的最低金额。约翰知道他可以以各种不同的顺序切割板，这将导致不同的费用，因为所得到的中间板具有不同的长度。

输入

第1行：一个整数N，木板的数量

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

输出

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

样例输入

    3
    8
    5
    8

样例输出

34

解题思路

这个题本质还是哈夫曼树的应用,以题中例子为例:第二刀:13 ==>>5 , 8 ,第一刀: 21 >> 13,8,总费用为13+21=34.如果其他切法,第二刀:16>>8,8 第一刀: 21 ==>> 16 ,5总费用21+16=37,我们想到了哈夫曼树的WPL.WPL就是最小值.

总木板长度为:8+5+8=21,如果切一刀后切的两块分别为13,8,第一刀费用就为13+8=21;然后再把13继续切成5和8,那么第二刀费用就为5+8=13.这是正面考虑.从题目角度考虑,切成n个木块总费用就是所形成的二叉树新生成节点的频率之和.13+21=34.而当该树为哈夫曼树时,频率之和最小.

注意:

①当N=1时,费用就是该木块的长度.题目的意思是我有很长的木板,但我需要长度(比如50),那么费用就是50.并不是说我需要一块我也正好有一块木板,那么我就不需要朋友来切了.

②这个题还用到了优先队列,不熟悉的朋友记得回去再熟悉下这个知识点哦.

③要注意题目中数据的范围,比如求费用时,如果都去最大值,则20000*50000=10^9 int可能就不够用了(按说勉强可以,但通不过),我用的是long long.

参考代码

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > Q;
int n,weight;
long long total;
int main()
{
  cin>>n;
  while(n--){
    cin>>weight;
    Q.push(weight);
  }
  if(n==1){
    total = weight;
  }else{
    while(Q.size() > 1){
      int w1 = Q.top();
      Q.pop();
      int w2 = Q.top();
      Q.pop();
      Q.push(w1+w2);
      total += w1+w2;
    }
  }
  cout<<total<<endl;
  return 0;
}