丹东谁家做网站,游戏排行,网站备案管理系统网站,网站建设关于我们/* 哈弗曼编码#xff0c;比如权值为 a:1 b:1 c:2 d:3 e:5 f:6 的树 1.开始时由最小的两个数 a:1 b:1组成一棵树 2.接着由新的最小的两个数 2 c:2 d:3 e:5 f:6 中的 2 c:2组成新的树 3.接着由最小的两个数 4 d:3 组成新的树 4.接着由最小的两个数 e:5 f:6 组成一棵树 5.接着由…/* 哈弗曼编码比如权值为 a:1 b:1 c:2 d:3 e:5 f:6 的树 1.开始时由最小的两个数 a:1 b:1组成一棵树 2.接着由新的最小的两个数 2 c:2 d:3 e:5 f:6 中的 2 c:2组成新的树 3.接着由最小的两个数 4 d:3 组成新的树 4.接着由最小的两个数 e:5 f:6 组成一棵树 5.接着由最小的两个数 7 11 组成一棵树最终形成 6.算最小的编码总长 18 7 11 4 2 42 2 4 7 11 18 / \ / \ / \ / \ / \ a b 2 c 4 d e f 7 11 / \ / \ / \ / \ a b 2 c 4 d e f / \ / \ a b 2 c / \ a b 可以用优先队列做优先队列每次插入都是插入到排完序后的队列数组中(可能不是很准确) 当还没开始建树时把出现的次数进队当开始建树时每次调用头两个数据a和b然后把两个数据 相加后再次进队同时优先队列会进行排序并且每次ans ab,最终答案即为ans */ #include iostream #include string #include queue #include vector using namespace std; string s; int main() { freopen(sum.in,r,stdin); freopen(sum.out,w,stdout); int n,command; while(cinn) { priority_queueint ,vectorint,greaterint q; //注意此处 是有空格的 int worst 0,ans 0; for(int i0;in;i) { cinscommand; worstcommand*s.size(); //最坏情况需要的空间 q.push(command); //把数据进队 } int a,b; if(q.size()1) //当之有一个串时 ans q.top(); while(true) { a q.top(); q.pop(); if(q.empty()) //只剩下一个根节点就已经构成了一棵树 break; b q.top(); q.pop(); ansab; //答案 q.push(ab); //把新生成的树的权值进队 } coutworst ansendl; } return 0; } poj3253Fence Repair #include iostream #include queue #include vector using namespace std; int main() { freopen(sum.in,r,stdin); freopen(sum.out,w,stdout); int n,t,a,b; while(cinn) { long long ans 0; //要为long long型才不会WA priority_queueint ,vectorint,greaterint q; for(int i0;in;i) { cint; q.push(t); } if(q.size()1) ans q.top(); while(q.size()1) { a q.top(); q.pop(); b q.top(); q.pop(); ans ab; q.push(ab); } coutansendl; } return 0; } 转载于:https://www.cnblogs.com/yejinru/archive/2012/03/21/2410367.html
