POJ 15221 Entropy

题目链接：POJ 1521【Entropy 】

思路

       典型哈夫曼树，求哈夫曼树的带权路径长度。

代码

#include <iostream>
#include <queue>
#include <string>
#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

int main() {
  string s;
  priority_queue<int, vector<int>, greater<int> > q;
  while (getline(cin, s)) {
    if (s == "END")
      break;

    int num = 1;
    sort(s.begin(), s.end());
    for (int i = 0; i < s.length(); i++) {
      if (s[i] != s[i + 1]) {
        q.push(num);
        num = 1;
      } else {
        num++;
      }
    }

    int ans = 0;
    if (q.size() == 1)
      ans = q.top();
    
    while (q.size() > 1) {
      int a = q.top();
      q.pop();
      int b = q.top();
      q.pop();
      q.push(a + b);
      ans += (a + b);
    }
    q.pop();

    printf("%d %d %.1f\n", 8 * s.length(), ans, 8.0 * s.length() / ans);
  }
  return 0;
}