文章

85

粉丝

0

获赞

315

访问

6.1k

头像
哈夫曼编码 题解:
P1562
发布于2026年3月5日 18:53
阅读数 71

#include <bits/stdc++.h>

using namespace std;
int anum[27];

int getval() {
    priority_queue<int,vector<int>,greater<int> >q;
    for (int i=0;i<27;i++) {
        if (anum[i]!=0) {
            q.push(anum[i]);
        }
    }
    int ans =0;
    if (q.size()==1) {return q.top();}
    while (q.size()>1) {
        int a=q.top();q.pop();
        int b=q.top();q.pop();
        int c =a+b;
        q.push(c);
        ans+=c;
    }
    return ans;
}


int main() {
    string s;
    while (getline(cin,s)&&s!="END") {
        memset(anum,0,sizeof(anum));
        for (char c:s) {
            if (c>='A' && c<='Z') {
                anum[c-'A']++;
            }
            if (c=='_') {
                anum[26]++;
            }
        }
        int ans = getval();
        double t = 8*s.length();
        printf("%g %d %.1f\n",t,ans,t/ans);
    }
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发