Input输入有多组case,首先是一个数字n表示有n组数据,然后每一组数据是有一个数值m(integer),和一串字符串没有空格只有包含小写字母组成!Output如果字符串的编码值小于等于给定的值则输出yes,否则输出no。
Sample Input
2 12 helloworld 66 ithinkyoucandoit
Sample Output
no yes
就是用哈夫曼树的思想求出新建的非叶子节点的权值之和,然后与m进行比较,若比m小,则是安全的。
#include<iostream> #include<cstdio> #include<map> #include<algorithm> #include<cstring> #include<queue> using namespace std; priority_queue<int,vector<int>,greater<int> >q; int main() { int t; while(cin>>t){ while(t--){ int m,len=0,a[100001]; memset(a,0,sizeof(a)); string str; cin>>m>>str; for(int i=0;i<str.size();i++){ a[str[i]-‘a‘]++; } for(int i=0;i<26;i++){ if(a[i]!=0){ q.push(a[i]); len++; } } int sum=0; while(q.size()>1){ int min1=q.top(); q.pop(); int min2=q.top(); q.pop(); sum+=min1+min2; q.push(min1+min2); } if(len==1){//注意此处的特殊情况 sum=q.top(); } if(m<=sum) cout<<"no"<<endl; else cout<<"yes"<<endl; while(!q.empty()){ q.pop(); } } } return 0; }
HDU2527 Safe Or Unsafe(哈夫曼的一道简单题)
原文:https://www.cnblogs.com/LJHAHA/p/11158765.html