题意：将一块木板切成N块，长度分别为：a1,a2,……an，每次切割木板的开销为当前木板的长度。求出按照要求将木板切割完毕后的最小开销。
思路：比较奇特的贪心
每次切割都会将当前木板一分为二，可以按切割要求画出二叉树。
总开销 = 各叶子节点的值 x 该叶子节点的深度
树的深度一定，为了使总开销尽可能的小，那么比较深的叶子节点的值应尽可能的小，所以二叉树应为：
模拟出所建立的二叉树，求出根节点的值即可
为了节省时间，可以利用优先队列每次取出最小的两个值合并，并将两数之和重新加入数组，直到数组内的元素个数为一时结束，时间复杂度为O(nlogn)。
#include<stdio.h> #include<queue> #include<iostream> #include<algorithm> #include<math.h> #include<string.h> #define INF 0x3f3f3f3f #define LL long long #define MOD 100000007 #define MAXSIZE 20005 using namespace std; int n,a[MAXSIZE]; LL Solve() { LL ans = 0; priority_queue<int,vector<int>,greater<int> >Q; for(int i=1;i<=n;i++) Q.push(a[i]); while(n > 1) { int minn1 = Q.top(); Q.pop(); int minn2 = Q.top(); Q.pop(); ans += (minn1 + minn2); Q.push(minn1 + minn2); n--; } return ans; } int main() { while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); LL ans = Solve(); printf("%lld\n",ans); } return 0; }
原文：http://www.cnblogs.com/alan-W/p/7188332.html
