哈夫曼树、哈夫曼编码



前言

哈夫曼树思想，其实一直都在用，只是这次才知道，这个东西叫做“哈夫曼树”
目前没做到有关真的建树的题目，都是考思想

  1. 哈夫曼树 与 哈夫曼编码
    http://www.cnblogs.com/kubixuesheng/p/4397798.html
    https://blog.csdn.net/xgf415/article/details/52628073

Entropy - HDU 1053

题目大意
求字符串转换为二进制后所占总位数值，进行编码后字符串总位数的最小值，以及两者的比

思路
裸的哈夫曼
注意不要先给队列压个0,因为会影响其他字符的编码位数

  #include <iostream>
  #include <cstdio>
  #include <queue>
  #include <functional>
  #include <algorithm>
  #include <cstring>
  using namespace std;
  const int N = 1e5 + 15;

  int cnt[128];
  char s[N];
  priority_queue<int, vector<int>, greater<int> > que;

  int main(){
      while(scanf("%s", s) && strcmp(s, "END") != 0){
          while(!que.empty())     que.pop();
          memset(cnt, 0, sizeof(cnt));
          int ans = 0;
          int len = strlen(s);

          for(int i = 0; i < len; i++){
              cnt[(int)s[i]]++;         //统计个字符出现次数
          }

          for(int i = 0; i < 128; i++){
              if(cnt[i])  que.push(cnt[i]);   //以次数建树，哈夫曼树思想
          }
          if(que.size() == 1){
              ans += que.top();       //只有一个元素建不了树，要特判
          }else{
              while(que.size() >= 2){
                  int x = que.top();
                  que.pop();
                  int y = que.top();
                  que.pop();
                  que.push(x + y);
                  ans += x + y;       
                  //画图可知，x和y最终给ans加的次数刚好等于其哈夫曼编码的位数，特别巧妙！
              }
          }
          printf("%d %d %.1f\n", len << 3, ans, (double)(len << 3)/ans);
      }
      return 0;
  }


Fence Repair - POJ 3253

题目大意
切割总长为 sigma(a[i]) 的木头， 最终切成 a[i]， 每次切割的代价为当前这块木头的长度，求怎样切割总代价最小

思路
裸的哈夫曼
本题考哈夫曼树的思想
注意开long long，不然结果溢出会WA

  #include <iostream>
  #include <cstdio>
  #include <queue>
  #include <functional>
  #include <algorithm>
  #include <cstring>
  using namespace std;
  typedef long long ll;

  priority_queue<ll, vector<ll>, greater<ll> > que;

  int main(){
      int n;
      while(~scanf("%d", &n)){
      	  while(!que.empty())   que.pop();
          ll ans = 0;
          while(n--){
          	int tmp;
          	scanf("%d", &tmp);
          	que.push(tmp);
          }
          while(que.size() >= 2){
              ll x = que.top();
              que.pop();
              ll y = que.top();
              que.pop();
              que.push(x + y);
              ans += x + y;
          }
          printf("%lld\n", ans);
      }
      return 0;
  }


Stripies - POJ 1862

题目大意
给定n个值，每次可选择其中两个值合并，合并的后的值为 2*sqrt(m1*m2)，直到剩下一个值，问这个值最小能是多少

思路
这道题我是蒙着AC的，事后问了一下大佬，被大佬一句话点醒
这道题的贪心策略是每次选择最大的两个值合并，因为乘2对最终结果是没什么影响的，有影响的是sqrt，那么数被越早的选择，它被开方的次数就越多，所以应该尽早的选择较大的数

  #include <iostream>
  #include <cstdio>
  #include <queue>
  #include <functional>
  #include <algorithm>
  #include <cstring>
  #include <cmath>
  using namespace std;
  typedef long long ll;

  priority_queue<double, vector<double>, less<double> > que;

  int main(){
      int n;
      while(~scanf("%d", &n)){
      	  while(!que.empty())   que.pop();
          double ans = 0;
          while(n--){
          	double tmp;
          	scanf("%lf", &tmp);
          	que.push(tmp);
          }
          while(que.size() >= 2){
              double x = que.top();
              que.pop();
              double y = que.top();
              que.pop();
              que.push(2*sqrt(x * y));
              ans += 2*sqrt(x * y);
          }
          printf("%.3f\n", que.top());
      }
      return 0;
  }


Boxes And Balls - CodeForces-884D

题目大意
有n个盒子，第一个盒子有许多不同颜色的球，剩下的盒子没有球。现在要把第i种颜色的球全部分到第i个盒子里面，要求每次从一个盒子里拿出全部球，并将这些球的个数作为每次的代价，然后把这些球放到k个盒子里面，k=2或3,问选择怎样的策略才能使总代价最小

思路
这题我还真是傻了去查题解
其实正向很难思考，可以反向思考：每次从k=2或3个盒子里面选出所有的数，加到某个空盒子里面，这些数的和为每次的代价，这样就转变为哈夫曼树
然后k=3自然是优于k=2的，然后因为这个合并策略是每次减3个数加1个数，所以当输入的数有偶数个时，可加一个0,使其变为奇数，这样就能每次-2直到剩下一个数

  #include <cstdio>
  #include <iostream>
  #include <algorithm>
  #include <cstring>
  #include <cctype>
  #include <queue>
  #include <functional>
  using namespace std;
  typedef long long ll;
  priority_queue<ll, vector<ll>, greater<ll> > que;

  int main(){
      int n;
      while(~scanf("%d", &n)){
          while(!que.empty())     que.pop();
          ll tmp;
          ll ans = 0;
          if((n&1) == 0)  que.push(0);
          while(n--){
              scanf("%lld", &tmp);
              que.push(tmp);
          }
          while(que.size() > 1){
              ll tmp = que.top();
              que.pop();
              tmp += que.top();
              que.pop();
              tmp += que.top();
              que.pop();
              ans += tmp;
              que.push(tmp);
          }
          printf("%lld\n", ans);
      }
  }