今天开始学习学习哈夫曼树，于是就去找点题目做做，毕竟学数据结构这种东西还是让oj来验证你的想法最方便了。
google了一下，pku的3252貌似是个软柿子，捏之～
看了一些关于哈夫曼的介绍，大致有个想法了，打出来，wa。。。看来想错了。
于是再看资料，发现需要动态寻找最小的两个节点的，于是就写了一个比较暴力的，参考网上的资料。
6365627 zerob13 3253 Accepted 236K 250MS C++ 628B 2010-01-24 15:08:06
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #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;i<n;i++) { scanf("%d",&lef[i]); } qsort(lef,n,sizeof(int),cmp); long long int sum=0; for(i=1;i<n;i++) { lef[i]+=lef[i-1]; sum+=lef[i]; k=lef[i]; for(j=i+1;j<n;j++) { if(k>lef[j]) { lef[j-1]=lef[j]; }else { break; } } lef[j-1]=k; } printf("%lld\n",sum); } return 0; } |
但是很不爽阿，感觉这种代码不是我的风格，于是打算用stl重新写一遍，于是我就开始用stl折腾了。。。
之后就出了一个效率好多了的stl版本。。。
6365653 zerob13 3253 Accepted 348K 32MS C++ 819B 2010-01-24 15:18:24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include<stdio.h> #include<string.h> #include<queue> #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< (node n1, node n2) { return n1.a > n2.a; } }; priority_queue<node>zerob; 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;i<n;i++) { scanf("%d",&lef); kk.a=lef; zerob.push(kk); } long long int sum=0; while(zerob.size()>1) { 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; } |
评论:2
参与评论