5.2.8 Safe Or Unsafe

Safe Or Unsafe

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 90 Accepted Submission(s): 50

Problem Description

Javac++ 一天在看计算机的书籍的时候，看到了一个有趣的东西！每一串字符都可以被编码成一些数字来储存信息，但是不同的编码方式得到的储存空间是不一样的！并且当储存空间大于一定的值的时候是不安全的！所以Javac++ 就想是否有一种方式是可以得到字符编码最小的空间值！显然这是可以的，因为书上有这一块内容--哈夫曼编码(Huffman Coding)；一个字母的权值等于该字母在字符串中出现的频率。所以Javac++ 想让你帮忙，给你安全数值和一串字符串，并让你判断这个字符串是否是安全的？

Input

输入有多组case，首先是一个数字n表示有n组数据，然后每一组数据是有一个数值m(integer)，和一串字符串没有空格只有包含小写字母组成！

Output

如果字符串的编码值小于等于给定的值则输出yes，否则输出no。

Sample Input

2
12
helloworld
66
ithinkyoucandoit

Sample Output

no
yes

思路：和上题基本一样，详见上题。

 1 #include <cstdio>
 2 #include <cstring>   
 3 #include <iostream>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <queue>
 7 using namespace std;
 8 
 9 struct cmp
10 {
11     bool operator () (const int a,const int b)
12     {
13         return a>b;
14     }
15 };
16 
17 const int maxl=100010,maxn=36;
18 priority_queue<int,vector<int>,cmp> q;
19 int n,t,ans,min1,min2,safe,l;
20 int a[maxn];
21 char s[maxl];
22 
23 void close()
24 {
25     exit(0);
26 }
27 
28 void judge()
29 {
30 //    printf("ans:%d\n",ans);
31     if (ans>safe)
32     printf("no\n");
33     else printf("yes\n");
34 }
35 
36 void work()
37 {
38     while (!q.empty())
39         q.pop();
40     for (int i=1;i<=26;i++)
41     {
42         if (a[i]!=0)
43             q.push(a[i]);
44     }
45     if (q.size()==1)
46     {
47         ans=q.top();
48         judge();
49         return;
50     }
51     while (!q.empty() && q.size()!=1)
52     {
53         min1=q.top();
54         q.pop();
55         min2=q.top();
56         q.pop();
57         ans+=min1+min2;
58         q.push(min1+min2);
59     }
60     judge();
61 
62 }
63 
64 void init()
65 {
66     while (scanf("%d",&t)!=EOF)
67      {
68          while (t--)
69          {
70              ans=0;
71              memset(a,0,sizeof(a));
72              scanf("%d",&safe);
73              scanf("%s",s);
74              l=strlen(s);
75              for (int i=0;i<l;i++)
76                  a[s[i]-'a'+1]++;
77              work();
78          }
79      }
80 }
81 
82 
83 int main ()
84 {
85     init();
86     close();
87 }