http://poj.org/problem?id=3253
没切一块板子 消耗的钱 等与这块板子的长度
要求最小钱的消耗
// 本题求最小money恰好构成一棵二叉树(霍夫曼?)
//总之 money = ∑(i = 0 to n) 叶子*深度
//每次选择 最小的两个叶子构成新的叶子
具体解决的问题 --->>>如何获取 两个最小的叶子并插入 新的叶子
每次sort的 话O(n^2logn)会超时
用prioroty_queue即可
顺便普及一下 对优先队列 元素各种自定义排序的写法
http://blog.sina.com.cn/s/blog_4e5157120100vn7b.html
1 #include <iostream> 2 #include <stdio.h> 3 #include <vector> 4 #include <algorithm> 5 #include <queue> 6 7 using namespace std; 8 9 bool cmp(int x, int y) 10 { 11 return x < y; 12 } 13 vector<int> v; 14 priority_queue< int,vector<int>,greater<int> > que;//小顶堆 tip : 如何自定义堆的排序 15 //注意数据量 int 就错了 要long long 才行 16 17 long long solve() 18 { 19 int m1, m2; 20 int temp; 21 long long sum = 0; 22 while (que.size() > 1) 23 { 24 m1 = que.top(); 25 que.pop(); 26 m2 = que.top(); 27 que.pop(); 28 temp = m1+m2; 29 sum += temp; 30 que.push(temp); 31 } 32 return sum; 33 } 34 int main() 35 { 36 int n,temp; 37 freopen("in.txt", "r", stdin); 38 while(~scanf("%d", &n)) 39 { 40 //v.clear(); 41 for (int i = 0; i < n; i++) 42 { 43 scanf("%d", &temp); 44 que.push(temp); 45 } 46 printf("%lld\n",solve()); 47 } 48 }
原文：http://www.cnblogs.com/oscar-cnblogs/p/6298509.html