【NOI2015】荷马史诗
因为不能有前缀关系，所以单词均为叶子节点，就是K叉哈夫曼树。第一问直接求解，第二问即第二关键字为树的高度。
#include< cstdio >
#include< algorithm > typedef unsigned long long ull;
template
inline void read(T&x)
{
x=0;bool f=0;char c=getchar();
while((c<'0'||c>'9')&&c!='-')c=getchar(); if(c=='-')f=1,c=getchar();
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x=f?-x:x;
}
const int MAXN(100010);
struct Data
{
ull val;int dep;
inline bool operator <(const Data &A)const {return (val==A.val)?dep>A.dep:val>A.val;}
}h[MAXN],New;int top;
int n,k,First;ull Ans,sum,w[MAXN];
void umax(int &a,int b){if(a<b)a=b;}
int main()
{
// freopen("C.in","r",stdin);
// freopen("C.out","w",stdout);
read(n);read(k);
for(int i=1;i<=n;i++)read(w[i]),sum+=w[i];
for(int i=1;i<=n;i++)h[++top]=(Data){w[i],1};
std::make_heap(h+1,h+1+top);
First=(n-1)%(k-1) +1;
// printf("%d\n",First);
// printf("%llu\n",sum);
if(First>1||n==1)
{
for(int i=1;i<=First;i++)
{
New.val+=h[1].val;
Ans+=h[1].val;
umax(New.dep,h[1].dep);
std::pop_heap(h+1,h+1+top);top--;
}
New.dep++;h[++top]=New;
std::push_heap(h+1,h+1+top);
}
while(top>1)
{
New.val=New.dep=0;
for(int i=1;top&&i<=k;i++)
{
New.val+=h[1].val;
Ans+=h[1].val;
umax(New.dep,h[1].dep);
std::pop_heap(h+1,h+1+top);top--;
}
New.dep++;
// printf("%llu %d\n",New.val,New.dep);
h[++top]=New;
std::push_heap(h+1,h+1+top);
}
printf("%llu\n",Ans);
printf("%d\n",h[1].dep-1);
return 0;
}