1 #include<iostream> 2 #include<iomanip> 3 #define N 27 4 using namespace std; 5 int cmp(const void *a,const void *b) 6 { 7 return *(int *)b-*(int *)a; //从大到小排序，方便对最小次小值的 操作 8 } 9 int main() 10 { 11 string s; 12 int num[27],a[27]; 13 int i,j,wpl,len; 14 while(cin>>s,s!="END"){ 15 memset(num,0,sizeof(num)); 16 for(i=0;s[i];++i){ 17 if(s[i]=='_') num[26]++; 18 else num[s[i]-'A']++; 19 } 20 len=i; 21 qsort(num,N,sizeof(int),cmp); 22 for(i=0;i<N&&num[i];++i) 23 a[i]=num[i]; 24 for(wpl=0,j=i-1;j>0;--j){ //核心代码！ 每次把最小的那个加到次小的上面，然后把加后的值计入到wpl中，再排序！ 25 a[j-1]+=a[j]; 26 wpl+=a[j-1]; 27 qsort(a,j,sizeof(int),cmp); 28 } 29 if(i==1) wpl=len; //注意，只有一种字母的时候，是个特殊情况 30 cout<<8*len<<" "<<wpl<<" "<<fixed<<setprecision(1)<<8.0*len/wpl<<endl; 31 } 32 return 0; 33 }
这道题是周赛的时候看到的，当时虽然懂得哈弗曼编码的思想与算法，觉得必须建一棵树，然后遍历所有叶子节点，只要求出各个叶子的深度，然后求wpl就容易了，但其中过程有些复杂，太耗时间了，所以我放弃了，但现在反过来再看它，其实没必要建一棵树，直接把每次新生成节点的权都加起来就行了，这样深度为n的叶子节点自然就加了n次啦！在本题中我用的是快速排序，其实快速排序在这题中有点不合适，快速排序属于交换类排序，交换类排序要想得到最小次小的数，需要全部排序，而本题恰恰只需要得到最小次小的就行了，所以本题用选择类排序最好了，如：简单选择排序，堆排序等！我是为了使代码精简所以使用了系统自带的qsort函数！！