Safe Or Unsafe
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1239 Accepted Submission(s): 484
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
这几天在忙着看二叉树，，，╮(╯▽╰)╭ 理解能力有待加强，，，
这道题的意思是 m与哈弗曼树除了叶子的权值（非叶子节点的权值之和）；用优先队列模拟哈弗曼树；
/* 题意:就是给你一个字符串如：12 helloworld统计出其中d:1个，e：1个，h:1个，l：3个，o：2个，r:1个，w：1个,
然后用一个数组保存起来a[7]={1,1,1,1,1,2,3};然后就是用哈夫曼树的思想求出新建的非叶子节点的权值之和：sum与12相比较
如果sum小于等于12的话就输出yes否则输出no，此案例求出的sum=27；所以输出no。
思路：按照建立哈夫曼树的思路每次求出两个的权值用min1保存最小的，min2保存次小的，
然后（min1+min2）加入其中，但是min1和min2需要踢出去，此题我用优先队列做的，就是
每次弹出最小的（min1）和次小的(min2)，然后把(min1+min2)压入队列中。//题中a=min1；b=min2；
但是有一组很坑爹的测试数据，开始的时候一直错，5 aaaaa 输出的是yes，5 aaaaaa输出的是no*/
#include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<iostream> using namespace std; priority_queue<int, vector<int>, greater<int> >Q;//从小到大，优先队列 char str[10001]; int huf[26]; int n; void solve() { int ans=0; int a,b; while(Q.size()!=1) { a=Q.top();//优先队列区最小的数（认为已经排好顺序了） Q.pop(); b=Q.top(); Q.pop(); Q.push(a+b);//把新的根入队； ans+=(a+b);//本题要求的权值； } printf(ans<=n?"yes ":"no "); } int main() { int T,i,len; scanf("%d",&T); while(T--) { while(!Q.empty())//保证队列为空 Q.pop(); memset(huf,0,sizeof(huf)); scanf("%d",&n); scanf("%s",str); len=strlen(str); for(i=0;i<len;i++) { huf[str[i]-'a']++;//统计各个字母的个数 } for(i=0;i<26;i++) if(huf[i])//如果有字母就入队 Q.push(huf[i]); if(Q.size()==1)//没有子叶的情况 { int m=Q.top(); Q.pop(); printf(m<=n?"yes ":"no "); } else solve(); } return 0; }
我的一道树的题目，纪念一下我的入门，，，哈哈
下面是用哈弗曼树写的，有点麻烦；感觉还是优先队列模拟的好，不过也可以参考一下哈
#include<iostream> #include<cstring> #include<cstdlib> using namespace std; struct node { int weight; int parent,left,right; }; char a[100001]; int huf(int str[],int size) { int i,lenth=2*size,min1,min2,x,y,sum=0,j; struct node *hf; hf=(struct node *)malloc(lenth*sizeof(struct node));//开创 for(i=size;i<lenth;i++) { hf[i].weight=str[i-size]; hf[i].parent=hf[i].left=hf[i].right=0; } for(i=size-1;i>0;i--) { min1=min2=10000000; x=y=0; for(j=i+1;j<lenth;j++) { if(min1>hf[j].weight&&hf[j].parent==0) { min2=min1; y=x; min1=hf[j].weight; x=j; } else if(min2>hf[j].weight&&hf[j].parent==0) { y=j; min2=hf[j].weight; } } hf[i].weight=min1+min2; sum=sum+hf[i].weight; hf[i].parent=0; if(x>y) swap(x,y); hf[i].left=y; hf[i].right=x; hf[x].parent=i; hf[y].parent=i; } return sum; } int main() { int T,n,i,j,len,num[26],b[26]; while(scanf("%d",&T)!=EOF) { while(T--) { len=0; memset(b,0,sizeof(b)); scanf("%d",&n); getchar(); scanf("%s",a); for(i=0;a[i]!=' ';i++) b[a[i]-'a']++;//把字母个数存入数组 for(i=0;i<26;i++) if(b[i]!=0) num[len++]=b[i];//除去空字母 if(len==1) { if(num[0]<=n) printf("yes "); else printf("no "); } else { if(huf(num,len)<=n) printf("yes "); else printf("no "); } } } return 0; }