题面：

追逐影子的人，自己就是影子 ——荷马

Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》 组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有n种不同的单词，从1到n进行编号。其中第i种单 词出现的总次数为wi。Allison 想要用k进制串si来替换第i种单词，使得其满足如下要求：

对于任意的 1 ≤ i, j ≤ n ， i ≠ j ，都有：si不是sj的前缀。

现在 Allison 想要知道，如何选择si，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison 还想知道最长的si的最短长度是多少？

一个字符串被称为k进制字符串，当且仅当它的每个字符是 0 到 k − 1 之间（包括 0 和 k − 1 ）的整数。

字符串 str1 被称为字符串 str2 的前缀，当且仅当：存在 1 ≤ t ≤ m ，使得str1 = str2[1..t]。其中，m是字符串str2的长度，str2[1..t] 表示str2的前t个字符组成的字符串。

题解：

如果学过huffman tree这题就不难了！

当然只知道huffman tree还是不行的，还要知道哈夫曼编码，

哈夫曼树貌似一开始就是用来获取哈夫曼编码的？

这个网上讲解很多，就不在多讲。

此题中如果按照出现次数为权值来构建哈夫曼树，则总长度一定最小，

原版哈夫曼树是2进制的，因此只能放2叉，

但这里是k进制，所以就可以放k叉了，

所以每次用优先队列找出前k小然后合并即可

但是要注意如果k != 2的话，就要保证每次合并都有k个节点（直到最后合并成一个），

所以要在最开始补一些空节点进去，

因为每次都是拿出k个，放入一个，所以实际上是消掉了（k-1)个，

然后最后需要剩下一个，因此我们需要n % (k-1) == 1,

然后补齐需要的即可

那为什么用出现次数作为权值就最优呢？

因为出现次数越大的单词越浅，所以编码长度也越小，自然总长度就最小了

但是这里还需要注意一个东西，就是第二问的要求，

需要最长的编码最短，依旧是用贪心的思想，

在权值相同的情况下，每次优先合并被合并次数少的节点（最深的节点更浅）

1 #include
     
        2 using namespace std;  3 #define R register int  4 #define    AC 100100  5 #define ac 500100  6 #define getchar() *o++  7 #define LL long long   8 char READ[5000100],*o=READ;  9 int n,k,id,deep; 10 int d[ac];//w为点权(包括新增点) 11 int Head[ac],Next[ac],date[ac],tot; 12 LL ans; 13 LL w[ac];//error!!!权值很大的啊 14 bool done; 15 struct cmp1{ 16     bool operator () (int &a,int &b) 17     { 18         if(w[a] != w[b])    return w[a] > w[b]; 19         else return d[a] > d[b]; 20     } 21 }; 22  23 priority_queue
      
       
        ,cmp1>q; 24 /*哈弗曼编码，这样是最短的，但无需获取具体的编码， 25 只要获得每个单词对应的出现次数（题目给定）和编码长度（哈弗曼树深度）即可， 26 因为是k进制，所以建立k叉哈弗曼树，最后dfs一遍获取每个叶节点的深度， 27 然后对出现次数与深度的积求和即可*/ 28 inline LL read() 29 { 30     LL x=0;char c=getchar(); 31     while(c > '9' || c < '0') c=getchar(); 32     while(c >= '0' && c <= '9') x=x*10+c-'0',c=getchar(); 33     return x; 34 } 35  36 inline void add(int f,int w) 37 { 38     date[++tot]=w,Next[tot]=Head[f],Head[f]=tot; 39 } 40  41 void dfs(int x,int dep) 42 { 43     int now; 44     if(!Head[x]) 45     { 46         ans+=(LL)dep * w[x]; 47         if(w[x]) deep=max(deep,dep); 48         return ;     49     } 50     for(R i=Head[x]; i ;i=Next[i]) 51     { 52         now=date[i]; 53         dfs(now,dep+1); 54     } 55 } 56  57 bool build() 58 { 59     if(done) 60         if(q.empty() || q.size() == 1) return false; 61     int x=++id,now;//动态加点 62     for(R i=1;i<=k;i++) 63     { 64         if(q.empty()) break; 65         now=q.top(); 66         q.pop(); 67         w[x] += w[now]; 68         d[x] = max(d[x] , d[now]); 69         add(x,now);//建树 70     } 71     ++d[x];//这次合并也要算啊 72     q.push(x); 73     done=true; 74     return true; 75 } 76  77 void pre() 78 { 79     n=read(),k=read(); 80     id=n; 81     for(int i=1;i<=n;i++)  82     { 83         w[i]=read(); 84         q.push(i); 85     } 86     if(k != 2)//但是只有不为二叉的时候才要考虑这些 87     { 88         int now=0; 89         if(!(n % (k-1)))//当余数为0的时候无需再跨越一次，，，，  90         { 91             q.push(++id); 92         }  93         else 94         if(n % (k-1) != 1) //huffman要求完美合并？ 95         { 96             now += (k-1) - (n % (k-1)) + 1; 97             for(R i=1;i<=now;i++) q.push(++id);//error!!!是权值为0，不是编号为0！！！ 98         } 99     }100 }101 102 void work()103 {104     while(build());105     dfs(id,0);106     printf("%lld\n",ans);107     printf("%d\n",deep);108 }109 110 int main()111 {112 //    freopen("in.in","r",stdin);113     fread(READ,1,5000000,stdin);114     pre();115     work();116 //    fclose(stdin);117     return 0;118 }