哈夫曼编码 - 追风蹑影
哈夫曼编码
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <stack> 9 #include <map> 10 #include <set> 11 #include <cmath> 12 #include <cctype> 13 #include <ctime> 14 15 using namespace std; 16 17 #define REP(i, n) for (int i = 0; i < (n); ++i) 18 #define eps 1e-9 19 #define SZ(x) ((int)x.size()) 20 #define PI acos(-1.0) 21 #define lc id << 1 22 #define rc id << 1 | 1 23 #define lson low, mid, lc 24 #define rson mid + 1, high, rc 25 26 typedef long long ll; 27 typedef unsigned long long ull; 28 typedef pair<int, int> pii; 29 const int maxn = 1e3; 30 char str[maxn]; 31 int T, n, len; 32 int cnt[maxn]; 33 multiset<int> s; 34 35 int huffman(char* str, int len, int k) { //k表示进制数 36 s.clear(); memset(cnt, 0, sizeof(cnt)); int ret = 0, t; 37 for (int i = 0; i < len; ++i) { ++cnt[str[i]]; } 38 for (int i = 0; i < 200; ++i) { 39 if (cnt[i]) { s.insert(cnt[i]); } 40 } 41 if ((int)s.size() == 1) { return *s.begin(); } 42 while ((int)s.size() > 1) { 43 t = 0; 44 for (int i = 0; i < k; ++i) { 45 t += *s.begin(); s.erase(s.begin()); 46 } 47 s.insert(t); ret += t; 48 } 49 return ret; 50 } 51 52 int main() { 53 #ifdef __AiR_H 54 freopen("in.txt", "r", stdin); 55 // freopen("out.txt", "w", stdout); 56 #endif // __AiR_H 57 scanf("%d", &T); 58 while (T--) { 59 scanf("%d %s", &n, str); 60 len = strlen(str); int ans = huffman(str, len, 2); 61 if (ans > n) { printf("no\n"); } 62 else { printf("yes\n"); } 63 } 64 return 0; 65 }
View Code
版权声明：本文为zhaoyz原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。