import java.util.*;
import java.io.*;
import java.lang.Math.*;
import java.text.DecimalFormat;
class Tree {
    public Tree left, right;
    public char value;
    public int frequency;
    public Tree (char value, int frequency) {
        this.value = value;
        this.frequency = frequency;
    }
    
    private void showTreedepth(Tree t, int depth) {
        if (t == null) return;
        showTreedepth(t.right, depth + 1);
        int i;
        for (i = 0 ; i < depth; i++) System.out.print("\t\t");
        System.out.println("(" + t.value + ", " + t.frequency + ")");
        showTreedepth(t.left, depth + 1);
    }
    
    public void showTree() {
        showTreedepth(this, 0);
    }
    
    public void preorder(int[] depth, int step) {
        if (this == null) return;
        if (this.left == null && this.right == null) {
            if (this.value == '_') {
                depth[26] = step;
            } else if (this.value >= 'A' && this.value <= 'Z') {
                depth[this.value - 'A'] = step;
            }
            return;
        }
        this.left.preorder(depth, step + 1);
        this.right.preorder(depth, step + 1);
    }
}

class NodeComparator implements Comparator<Tree> {
    @Override
    public int compare(Tree t1, Tree t2) {
        if (t1.frequency > t2.frequency) return 1;
        return -1;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str;
        int pl;
        double ratio;
        // DecimalFormat df = new DecimalFormat("###.0");
        while ((str = sc.nextLine())!= null) {
            if (str.compareTo("END") == 0) {
                break;
            }
            if (str.length() == 0) continue;
            pl = HuffmanPattern(str);
            ratio = (double) str.length() * 8.0 / (pl * 1.0);
        
            System.out.println(str.length() * 8 + " " + pl + " " + String.format("%.1f", ratio));
        }
    }
    
    public static int HuffmanPattern(String str) {
        Tree[] pattern = new Tree[27];
        int[] depth = new int[27];
        Tree t1 = null, root = null, t2 = null;
        int i;
        char ch;
        for (i = 0 ; i < 27; i++) {
            if (i != 26) {
                ch = (char) (65 + i);
                pattern[i] = new Tree(ch, 0);
            } else {
                pattern[i] = new Tree('_', 0);
            }
        }
        Comparator<Tree> cmp = new NodeComparator();
        PriorityQueue<Tree> queue = new PriorityQueue<Tree>(64, cmp);
        for (i = 0 ; i < str.length(); i++) {
            if (str.charAt(i) == '_') {
                pattern[26].frequency++;
            } else if (str.charAt(i) >= 'A' && str.charAt(i) <= 'Z') {
                pattern[str.charAt(i) - 'A'].frequency++;
            }
        }
        
        for (i = 0 ; i < 27; i++) {
            if (pattern[i].frequency != 0) {
                queue.add(pattern[i]);
            }
        }
        if (queue.size() == 0) return 0;
        if (queue.size() == 1) return queue.remove().frequency;
        // root = queue.peek();
        while (queue.size() > 1) {
            t1 = queue.remove();
            t2 = queue.remove();
            root = new Tree('0', t1.frequency + t2.frequency);
            root.left = t1;
            root.right = t2;
            queue.add(root);
        }
        root = queue.remove();
        root.preorder(depth, 0);
        
        int ans = 0;
        for (i = 0 ; i < 27; i++) {
            ans += depth[i] * pattern[i].frequency;
        }
        return ans;
    }
    
}

编译成功

foo.cpp: In function 'int main()':
foo.cpp:43:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i<a.size(); i++)
^
测试数据 #0: Accepted, time = 15 ms, mem = 276 KiB, score = 100
Accepted, time = 15 ms, mem = 276 KiB, score = 100

這是我過的第一百題，我交的就是合併果子的程序。

点击查看程序源码+详细题解