现在的位置: 首页 > 算法 > 正文

poj 1521

2017年11月23日 算法 ⁄ 共 958字 ⁄ 字号 评论关闭

 poj 1521 Entropy

#include <iostream>
#include <queue>
#include <string>
#include <stdio.h>
using namespace std;
string s;
int k=0;
struct node{
    int w;
    int parent;
    int key;
    friend bool operator < (const node & a,const node & b){
    if(b.w<a.w)return true;
    else return false;
    }
    }alp[60];
int value(char c){
    if(c=='_')return 26;
    else return c-'A';
    }
void huf(){
    int i,j;
    int length=s.length();
    priority_queue<node>q;
    for(i=0;i<length;i++)
    alp[value(s[i])].w++;
    for(i=0;i<=26;i++){
        if(alp[i].w!=0){
        q.push(alp[i]);
        }
    }
    if(q.size()==1)
    printf("%d %d 8.0\n",8*length,length);
    else {
         j=27;
        while(q.size()>1){
            node s1=q.top();
            q.pop();
            node s2=q.top();
            q.pop();
            alp[j].w=s1.w+s2.w;
            alp[s1.key].parent=j;
            alp[s2.key].parent=j;
            q.push(alp[j]);
            j++;
            }
        int res=0;
        for(int ii=0;ii<27;ii++){
             if(alp[ii].w!=0){
                int len=1;
                int par=alp[ii].parent;
                while(par!=j-1){
                    len++;
                    par=alp[par].parent;

                    }
                res+=len*alp[ii].w;
                }
            }
        double dd=8*length;
        printf("%d %d %.1lf\n",8*length,res,dd/res);
        }
    }
int main()
{
    while(cin>>s&&s!="END"){
        int i;
        for(i=0;i<60;i++){
            alp[i].w=0;
            alp[i].key=i;
            }
        huf();
        }

    return 0;
}

 

抱歉!评论已关闭.