今天开始学习学习哈夫曼树,于是就去找点题目做做,毕竟学数据结构这种东西还是让oj来验证你的想法最方便了。
google了一下,pku的3252貌似是个软柿子,捏之~
看了一些关于哈夫曼的介绍,大致有个想法了,打出来,wa。。。看来想错了。
于是再看资料,发现需要动态寻找最小的两个节点的,于是就写了一个比较暴力的,参考网上的资料。
6365627 zerob13 3253 Accepted236K250MS C++ 628B 2010-01-24 15:08:06

include<stdio.h> #include<string.h> #include<stdlib.h> int lef[20001]; int n; int cmp(const void a,const void b) { return (int)a-(int)b; } int main (int argc, char * const argv[]) { int i,j,k,l; while(scanf("%d",&n)!=EOF){ for(i=0;ilef[j]) { lef[j-1]=lef[j]; }else { break; } } lef[j-1]=k; } printf("%lld\n",sum); } return 0; } </stdlib.h></string.h></stdio.h>

但是很不爽阿,感觉这种代码不是我的风格,于是打算用stl重新写一遍,于是我就开始用stl折腾了。。。
之后就出了一个效率好多了的stl版本。。。
6365653 zerob13 3253 Accepted348K32MS C++ 819B 2010-01-24 15:18:24

include<stdio.h> #include<string.h> #include #include<stdlib.h> using namespace std; int lef; int n; int cmp(const void a,const void b) { return (int)a-(int)b; } struct node{ int a; friend bool operator n2.a; } }; priority_queuezerob; int main (int argc, char * const argv[]) { int i,j,k,l; node kk; while(scanf("%d",&n)!=EOF){ while(!zerob.empty()){ zerob.pop(); } for(i=0;i1) { node a=zerob.top(); zerob.pop(); node b=zerob.top(); zerob.pop(); sum+=a.a+b.a; kk.a=a.a+b.a; zerob.push(kk); } printf("%lld\n",sum); } return 0; } </stdlib.h></string.h></stdio.h>