多校联合 8.24 Encode

Encode

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)

Total Submission(s) : 14 Accepted Submission(s) : 3

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem DescriptionGiven a string S, you need to use N different characters will be encoded into a string.

InputLine 1: S Waiting for the encoded string (length<=100000 )
Line 2: N Use N characters to encode the S (N different characters 0<=N<=100000)

OutputYou need to print the length of the encoded(Minimum length encoded)

Sample Input

iloveacm2iloveacm4

Sample Output

2414

Authorshenlizhong

题意很简单，构造哈夫曼是两个字符0、1，这里是给你n个不同的字符给一个字符串加密。就是K路最佳合并（权值之和最小）。

代码：

#include<iostream>#include<map> #include<queue>char str[100005],n;using namespace std;int main(){    priority_queue<__int64,vector<__int64>,greater<__int64> > que;    map<char,int> mp;    map<char,int>::iterator it;    int k,i,len;    __int64 ans,ret;    while( gets(str)){ //题目中会有空格 Wrong了9次            char tt[12];           scanf("%d",&n);             gets(tt); //过滤换行           mp.clear();           len=strlen(str);           if(n==0){                    printf("%d\n",len);                    continue;           }           for( i=0;i<len;i++)                mp[str[i]]++;           ret=0;              if( mp.size()<=n)               ret=len;           else{                                         while(!que.empty()) que.pop();                                      for( it=mp.begin();it!=mp.end();it++)                        que.push((*it).second);                                              k=(mp.size()-1)%(n-1);  //构造k个权值为0的虚拟结点 进行K路合并                    if( k){                       k=(n-1)-k;                       while( k--) que.push(0);                    }                             while( que.size()!=1){                          ans=0;                          k=n;                          while( k--){   //取前K个最小的结点                                  ans+=que.top();                                 que.pop();                          }                          ret+=ans;                           que.push(ans);  //合并成一个虚拟结点。                    }          }          printf("%I64d\n",ret);    }           return 0; }

1楼sevenster昨天 21:16

完全被学妹超越了...