[文章目录]
Description
一部《荷马史诗》中有 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 个字符组成的字符串。
合并果子，添加了个结构体以及自定义比较级，手写heap水过。不过需要注意check的返回值代表前一项优于后一项，还是反之。对于合并k堆而不够的，我们添加几个空的单词，就搞定了。
据说这题是哈夫曼树的思想？？？
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n,k,fna;
struct node
{
ll w,t;
};
struct heap
{
node q[110000];
int now;
heap(){now=0;}
bool check(node x,node y)
{return x.w==y.w ? x.t<y.t : x.w<y.w ;}
void down(int x)
{
while((x<<1|1)<=now&&(check(q[x<<1],q[x])||check(q[x<<1|1],q[x])))
{
x= check(q[x<<1],q[x<<1|1]) ? x<<1 : x<<1|1;
swap(q[x],q[x>>1]);
}
if((x<<1)<=now&&check(q[x<<1],q[x])) swap(q[x],q[x<<1]);
}
void up(int x)
{
while(x>1&&check(q[x],q[x>>1]))
swap(q[x],q[x>>1]),x>>=1;
}
void push(node x) {q[++now]=x;up(now);}
void pop(){swap(q[1],q[now]);now--;down(1);}
int size(){return now;}
node top(){return q[1];}
void output()
{
puts("check");
for(int i=1;i<=now;i++)
printf("%lld %lld\n",q[i].w,q[i].t);
puts("end");
}
}q;
int main()
{
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++)
{
ll x;
scanf("%lld",&x);
q.push((node){x,0});
}
while(n%(k-1)!=1&&k!=2) n++,q.push((node){0,0});
while(q.size()!=1)
{
ll t=0,w=0;
for(int i=1;i<=k;i++)
{
node x=q.top();q.pop();
t=max(t,x.t);
w+=x.w;
}
q.push((node){w,t+1});
fna+=w;
}
printf("%lld\n%lld",fna,q.top().t);
return 0;
}