一 原题链接

Inverting Huffman - UVA 12676 - Virtual Judge

https://vjudge.net/problem/UVA-12676

二 输入和输出

输入样例

2

1 1

4

2 2 2 2

10

8 2 4 7 5 1 6 9 3 9
输出样例

2

4

89

三 算法设计

本问题不是简单的哈夫曼编码问题，而是反其道而行之，根据编码长度，推测最小字符数。

例如
4 // 表 4 个不同字符

3 1 2 3 // 每个字符编码长度

其最长编码为3，即深度为3.底层节点权值至少为1，每一层节点的权值至少是下一层节点权值的最大值。如果当前节点的权值比下一层节点权值小，就会出现在下一层了，因为权值越小，出现的层次越大，如下图所示。

1 在每一层都用一个深度数组 deep[] 记录该层节点的权值，将该层每个节点的权值都初始化为0，等待推测权值。
2 根据输入的编码长度算出最大长度，即哈夫曼树的最大深度 maxd。

3 从最大深度 maxd 向上计算并推测，直到树根。开始时 temp =1。

• i = maxd：第 i 层节点权值如果为0，则被初始为 temp。对第 i 层从小到大排序，然后将第i 层每两个合并，将权值放入上一层（i-1层）。更新 temp 为第 i 层排序后最后一个元素（最大元素）。
• i = max-1：重复上述操作。
• i = 0：结束，输出0层第1个元素。

四 实现

package tree;

import java.util.Collections;
import java.util.Scanner;
import java.util.Vector;

public class UVA12676 {
    public static void main(String[] args) {
        final int maxn = 55;
        Vector<Long> deep[] = new Vector[maxn];
        for (int i = 0; i < deep.length; i++) {
            deep[i] = new Vector<>();
        }
        int x;
        while (true) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            for (int i = 0; i < n; i++)
                deep[i].clear();
            int maxd = 0;
            for (int i = 0; i < n; i++) {
                x = scanner.nextInt();
                deep[x].addElement(0L);
                maxd = Math.max(maxd, x); // 求最大深度
            }
            long temp = 1;
            for (int i = maxd; i > 0; i--) {
                for (int j = 0; j < deep[i].size(); j++) {
                    if (deep[i].get(j) == 0)
                        deep[i].set(j, temp); // 将第i层最大的元素值赋值给 i-1 层没有权值的结点
                }
                Collections.sort(deep[i]); // 第i层排序

                for (int j = 0; j < deep[i].size(); j += 2)
                    deep[i - 1].addElement(deep[i].get(j) + deep[i].get(j + 1)); //合并后放入上一层
                temp = deep[i].get(deep[i].size() - 1); // 取第 i 层的最后一个元素，即第 i 层最大的元素
            }
            System.out.println(deep[0].get(0)); // 输出树根的权值
        }
    }
}

五 测试

绿色为输入，白色为输出