————ACM————|POJ3253 Fence Repair （二叉堆 | 优先队列 | huffman树 ) ACM|from|Vit|基础数据结构

本文出自：http://blog.csdn.net/svitter
题意：
给你几根木板，让你连接起来，每次连接花费为两根长度之和。连接所有的木板，最后最小的花费是多少。
【————ACM————|POJ3253 Fence Repair （二叉堆 | 优先队列 | huffman树 )】

输入输出分析：
略。

算法数据结构分析：
这个题目用贪心即可。即，每次的取两根最小的，花费最少，最后花费就最少。
本题目可以用二叉堆的最关键就在于二叉堆的定义：
大根堆：上面的比下面的大；
小根堆：上面的比下面的小；
通过一维数组最后一个添加或者删除，进行调整。

记于2014.08.01：
后来补充上优先队列的解法。
STL中的priority_queue就是使用的二叉堆实现的。
另外附上优先队列的使用方法：

struct cmp1 { bool operator ()(int &a,int &b) { return a>b; //最小值优先 } }; struct cmp2 { bool operator ()(int &a,int &b) { return aa.u; //最小值优先 } }; struct node2 { int u; bool operator < (const node2 &a) const { return uq1; //采用默认优先级构造队列 priority_queue,cmp1>q2; //最小值优先 priority_queue,cmp2>q3; //最大值优先 priority_queue,greater >q4; //注意“>>”会被认为错误， //这是右移运算符，所以这里用空格号隔开,最小值优先 priority_queue,less >q5; //最大值优先 priority_queueq6; //自定义优先级 priority_queueq7;

1.一般堆解法：
时间消耗：

————ACM————|POJ3253 Fence Repair （二叉堆 | 优先队列 | huffman树 )

文章图片

#include #include #include #include using namespace std; __int64 a[20010]; int m, n; void heap(int m) { int t; while(m * 2 <= n)//有子堆 { m = m * 2; if(m < n && a[m] > a[m+1]) // 较大的子堆 { m++; } if(a[m] < a[m / 2]) // { t = a[m]; a[m] = a[m/2]; a[m/2] = t; } else break; } }void push_heap() { int i = n; __int64 x = a[n]; while(i > 1 && a[i/2] > x) { a[i] = a[i/2]; i /= 2; } a[i] = x; }void pop_heap() { __int64 x; //swap top.root x = a[1]; a[1] = a[n]; a[n] = x; n--; heap(1); }void make_heap() { int i; for(i = n / 2; i > 0; i --)//从n/2构建即可 { heap(i); } }void ace() { int i; __int64 cur0, cur1, cur, sum; while(~scanf("%d", &n)) { for(i = 1; i <= n; i++) { scanf("%I64d", &a[i]); } make_heap(); sum = 0; while(n != 1) { pop_heap(); cur0 = a[n+1]; pop_heap(); cur1 = a[n+1]; cur = cur0 + cur1; sum += cur; a[++n] = cur; push_heap(); } printf("%I64d\n", sum); } }int main() { ace(); return 0; }

2.类似冒泡解法
时间消耗：

文章图片

#include #include #include #include using namespace std; __int64 a[20010]; int m, n; void ace() { int i; __int64 cur0, cur1, cur, sum; while(~scanf("%d", &n)) { for(i = 1; i <= n; i++) { scanf("%I64d", &a[i]); } make_heap(); sum = 0; while(n != 1) { pop_heap(); cur0 = a[n+1]; pop_heap(); cur1 = a[n+1]; cur = cur0 + cur1; sum += cur; a[++n] = cur; push_heap(); } printf("%I64d\n", sum); } }int main() { ace(); return 0; }

3.模板STL解法

#include #include #include #define lln long long using namespace std; struct item { lln w; bool operator < (const item &a)const { return w > a.w; } }; int n; int main() { item t; item t1, t2; int i; lln cost; priority_queue Queue; while(~scanf("%d", &n)) { for(i = 0; i < n; i++) { scanf("%lld", &t.w); Queue.push(t); }cost = 0; while(!Queue.empty()) { t1 = Queue.top(); Queue.pop(); if(Queue.empty()) break; t2 = Queue.top(); Queue.pop(); t1.w += t2.w; cost += t1.w; if(Queue.empty()) break; Queue.push(t1); } printf("%lld\n", cost); } return 0; }