哈夫曼编码

PTA哈夫曼编码

题意：

• 给定每个单词出现的频率，给出一套编码，判断是否满足哈夫曼编码。

题解：

• 通过单词出现的频率计算wpl。可以通过c++的stl优先队列快速处理。
• 然后计算编码的wpl是否满足，以及是否存在编码前缀嵌套的情况。

代码

#include <bits/stdc++.h>
using namespace std;
int const N = 65;
typedef pair<char,int>pii;
pii a[N];
string s[N];
map<char,int>mp;
int n;
priority_queue<int,vector<int>,greater<int> >q; //最小堆
int getwpl(){
    int wpl = 0;
    while(q.size() > 1){
        int x = q.top();    q.pop();
        int y = q.top();    q.pop();
        wpl += (x + y);
        q.push(x + y);
    }
    q.pop();
    return wpl;
}
bool isprefix(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(s[i].length() == s[j].length() && s[i] == s[j])  return false;
            if(s[i].length() < s[j].length() 
                && s[j].substr(0,s[i].length()) == s[i])  return false;
            if(s[j].length() < s[i].length() 
                && s[i].substr(0,s[j].length()) == s[j])  return false;
        }
    }
    return true;
}
bool judge(int wpl){
    int weight = 0;
    for(int i=1;i<=n;i++){
        char x;
        cin>>x>>s[i];
        weight += mp[x] * s[i].length();
    }
    if(wpl != weight)   return false;
    if(!isprefix()) return false;
    return true;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        char c;
        int x;
        scanf(" %c%x",&c,&x);
        mp[c] = x;
        q.push(x);
    }
    int wpl = getwpl();
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        if(judge(wpl)) printf("Yes\n");
        else    printf("No\n");
    }
    return 0;
}