洛谷2168 [NOI2015]荷马史诗

题意

用 $K$ 进制串 $S_i$ 表示 $N$ 个不同的单词。每个单词出现了 $W_i$ 次，不存在某个进制串是另一个的字串。

求处理后全文的最短长度，以及此情况下最长 $S_i$ 的最短长度。

题解

编码方式显然是一棵 $K$ 叉哈夫曼树，先补 $0$ 直到 $(N-1)\equiv 0\pmod {(K-1)}$ ，然后每次选 $K$ 个点合并成一个点直到只剩 $1$ 个点即可。

要求最长的 $S_i$ 最短，可以在堆中记录一个深度，如果 $W_i$ 相同就选深度小的点合并。

#include<bits/stdc++.h>
#define ll long long
#define pr pair<ll,ll>
#define mp make_pair

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,k,ans;
priority_queue <pr,vector<pr>,greater<pr> > q;

signed main()
{
    n=read(); k=read();
    for (ll i=1;i<=n;i++) q.emplace(mp(read(),1));
    ll ex=(n-1)%(k-1) ? k-1-(n-1)%(k-1) : 0;
    for (ll i=1;i<=ex;i++) q.emplace(mp(0,1));
    n+=ex;
    ex=(n-1)/(k-1);
    while (ex--)
    {
        ll res=0,mxh=0;
        for (ll i=1;i<=k;i++)
        {
            ll x=q.top().first,y=q.top().second; q.pop();
            res+=x;
            mxh=max(mxh,y);
        }
        ans+=res;
        q.emplace(mp(res,mxh+1));
    }
    return !printf("%lld\n%lld",ans,q.top().second-1);
}