学步园

最近每次做题都要看很多资料。看来是真的老了。

这题给定字符串，以及待编码的字符数，采用哈夫曼编码，编码总长度最短。求此值。

这题添加虚拟节点，使得最后的合并方便，也就是使得每次合并保证树中都大于T个。T为提供的编码字符数。

相当于每一个节点要么是空的要么是有T个孩子的。

设待编码字符为N，添加的虚节点个数为β。

那么对（N+β）进行一次合并-> (N+β)-T+1 第二次合并 （N+β）-2*（T-1）

......

最后一次(N+β)-r*(T-1)=1

也就是(N+β)%(T-1)==1%(T-1); 好像出现了同余...

下面代码基本上是段学妹的.. 我待会儿看看STL的一些个东西...

PS:据说priority_queue内部是用红黑树实现的,跪了....

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

bool cmp( int a,int b ){
 	 return a<b;
}

int main()
{
 	freopen( "K.in","r",stdin );
 	freopen( "ans.out","w",stdout );
 	char str[111111];
	int n;
    map<char,int> mp;
    map<char,int>::iterator it;
    
 	priority_queue< int,vector<int>,greater<int> >que;
 	while( gets(str) )
 	{
	 	   scanf( "%d",&n );
   		   getchar();
   		   mp.clear();
   		   for( int i=0;i<strlen(str);i++ )
   		   		mp[str[i]]++;
   		   		
	 	   while( !que.empty() ) que.pop();
			   		   
		   for( it=mp.begin();it!=mp.end();it++ )
		   		que.push((*it).second);
		   		
		   while( que.size()%(n-1)!=1%(n-1))
		   		  que.push(0);
		   
		   int ans=0;
		   if( mp.size()<=n )
		   	   ans = strlen(str);
		   else
		   {
		   		   while( que.size()!=1 )
		   		   {   
		   	   	       	  int su=0;
		   	   	  		  for( int i=0;i<n;i++ )
		   	   	  		  {
		   	   		   	   	   su+=que.top();
		   	   		   		   que.pop();
  	   		  			  }
		   	   	  		  ans+=su;
		   	   	  		  que.push(su);
	   			   }
		   }
   		   printf( "%d\n",ans );
  	}
 	return 0;
}