hdu/hdoj 1053 Entropy

195 阅读 0 评论 129 点赞

我是靠谱客的博主威武斑马，这篇文章主要介绍hdu/hdoj 1053 Entropy，现在分享给大家，希望可以做个参考。

题目大意：给你一个字符串，每一个字符在计算机中用8位编码表示，所以给你字符串AAAAABCD，它在计算机中要占用64位，可是为了节省内存，希望你能
设计出一种编码，使得内存的占用尽可能的少，即字符串的位数表示最少，输出原本占几位，编码后占几位，二者的商

复制代码

#include <iostream>
#include <queue>
#include <vector>
#include <stdio.h>
#include <string>
#include <cstring>
using namespace std;

struct kiss
{
    int kk;
    bool operator < (const kiss &a)
    {
        return kk>a.kk;
    }
}tmep[27];
priority_queue<int,vector<int>,greater<int> > que;
int main()
{
    string str;
    
    while (getline(cin,str),str!="END")
    {
        
        
        for (int i=0; i<27; ++i)
        {
            tmep[i].kk=0;
        }
        while(!que.empty())
            que.pop();

for (int i=0; i<str.length(); ++i)
        {
            if (str[i]=='_')
                tmep[26].kk++;
            else
                tmep[str[i]-'A'].kk++;
        }

for (int i=0; i<27; ++i)
        {
            if (tmep[i].kk!=0)
            {
                que.push(tmep[i].kk);
            }
        }
        int ans=0,a,b;
        if (que.size()==1)
        {
            
            que.pop();
            
            printf("%d %d 8.0n",str.length()*8,str.length());
        }

else
        {
            
        
            while(que.size()!=1)
            {
                a=que.top();que.pop();
                b=que.top();que.pop();
                  que.push(a+b);
                  ans+=(a+b);
                }
            printf("%d %d %.1lfn",str.length()*8,ans,str.length()*8.0/ans);
        }
        
    
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <queue>
#include <vector>
#include <stdio.h>
#include <string>
#include <cstring>
using namespace std;

struct kiss
{
    int kk;
    bool operator < (const kiss &a)
    {
        return kk>a.kk;
    }
}tmep[27];
priority_queue<int,vector<int>,greater<int> > que;
int main()
{
    string str;
    
    while (getline(cin,str),str!="END")
    {
        
        
        for (int i=0; i<27; ++i)
        {
            tmep[i].kk=0;
        }
        while(!que.empty())
            que.pop();

        for (int i=0; i<str.length(); ++i)
        {
            if (str[i]=='_')
                tmep[26].kk++;
            else
                tmep[str[i]-'A'].kk++;
        }

        for (int i=0; i<27; ++i)
        {
            if (tmep[i].kk!=0)
            {
                que.push(tmep[i].kk);
            }
        }
        int ans=0,a,b;
        if (que.size()==1)
        {
            
            que.pop();
            
            printf("%d %d 8.0n",str.length()*8,str.length());
        }


        else
        {
            
        
            while(que.size()!=1)
            {
                a=que.top();que.pop();
                b=que.top();que.pop();
                  que.push(a+b);
                  ans+=(a+b);
                }
            printf("%d %d %.1lfn",str.length()*8,ans,str.length()*8.0/ans);
        }
        
    
    }
}