Luogu 2168 [NOI 2015] 荷马史诗

传送门

思路

  唉，我太弱了，什么都不会，连哈夫曼树都不会。这道题就是一个 k k $k$ 叉哈夫曼树。

  题目要求满足两个条件，一是代价最小，二是最长长度最小。最长长度最小很好解决，只需要优先合并高度小的就可以了。如何解决代价最小的问题呢？

  k$k$$k$ 叉哈夫曼树的解决方法是：每次从堆顶选 k k $k$ 个最小的，给它们增加一个根结点，权值为那 k$k$$k$ 个结点的权值之和。但是有一个问题：二叉哈夫曼树的结点要么有两个儿子，要么没有儿子，但是 k k $k$ 叉哈夫曼树在最后可能结点数不足 k$k$$k$ 个。剩下的几个空位是在最上面的，肯定可以把其它结点移上来使得答案更优。

  但显然我们不能够手动移动，因为没有办法移出最优答案。观察发现，我们树的总数将会从 n n $n$ 变成 1$1$$1$；每次合并树的总数将会减少 k−1 k − 1 $k - 1$，因此只需要保证 k−1 k − 1 $k - 1$ 整除结点数，最后合并时得到的哈夫曼树就一定是满的。所以解决方法是在一开始增加空结点，直到 k−1 k − 1 $k - 1$ 整除结点数。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
    putchar('\n');
}

const int maxn = int(1e5) + 5;
int n, k;
LL a[maxn];

struct HeapNode
{
    LL w;
    int h;
    HeapNode(LL w, int h) : w(w), h(h) {}
    bool operator<(const HeapNode& b) const
    {
        if (w != b.w) return w > b.w;
        return h > b.h;
    }
};

void run()
{
    std::priority_queue<HeapNode> pq;
    n = readIn();
    k = readIn();
    for (int i = 1; i <= n; i++)
        pq.push(HeapNode(readIn(), 0));
    while ((pq.size() - 1) % (k - 1))
        pq.push(HeapNode(0, 0));

    LL ans = 0;
    while (pq.size() > 1)
    {
        LL sum = 0;
        int height = 0;
        for (int i = 1; i <= k; i++)
        {
            HeapNode t = pq.top();
            pq.pop();
            sum += t.w;
            height = std::max(height, t.h);
        }
        ans += sum;
        pq.push(HeapNode(sum, height + 1));
    }

    printOut(ans);
    printOut(pq.top().h);
}

int main()
{
    run();
    return 0;
}