POJ3253 Fence Repair 贪心

　　题目大意是，把一块长木板割成n快给定长度的木板，每次的花费为当前模板的长度，求最小的花费。逆向求解即可，贪心的思想，每次取两块木板长度最小的，花费为量长度之和，然后把新的长度加进去，操作n-1次，就是一个huffman树的构造过程。然后用优先队列搞之。

 1 //STATUS:C++_AC_16MS_348KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 using namespace std;
13 #define LL __int64
14 #define pii pair<int,int>
15 #define Max(a,b) ((a)>(b)?(a):(b))
16 #define Min(a,b) ((a)<(b)?(a):(b))
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define lson l,mid,rt<<1
19 #define rson mid+1,r,rt<<1|1
20 const int N=110,INF=0x3f3f3f3f,MOD=1999997;
21 const LL LLNF=0x3f3f3f3f3f3f3f3fLL;
22 
23 int n;
24 
25 int main()
26 {
27  //   freopen("in.txt","r",stdin);
28     int i,a,t;
29     LL ans;
30     while(~scanf("%d",&n))
31     {
32         priority_queue<int,vector<int>,greater<int> > q;
33         ans=0;
34         for(i=0;i<n;i++){
35             scanf("%d",&a);
36             q.push(a);
37         }
38         for(i=1;i<n;i++){
39             t=q.top();q.pop();
40             t+=q.top();q.pop();
41             ans+=t;
42             q.push(t);
43         }
44 
45         printf("%I64d\n",ans);
46     }
47     return 0;
48 }