【PTA】05-ツリー9 Huffman Codes(30分)優先キュー

タイトルリンク
考え方:
1.記録頻度
①符号化する文字を配列で記録する(char ch[N];)
②mapコンテナTimeを作成し、Time[文字]で文字の使用回数を記録する
2.ハフマンツリーを作成し、最小コストを算出
①優先キューでハフマンツリーを作る
②最小費用の計算(キュー層順でHuffmanツリーを巡る)
3.試験データの比較
①費用が最小かどうか---でなければ---->出力no(符号化長*文字使用回数)
②曖昧さがないか(接頭辞を比較しmap容器で、小さい頃から大きいまでマークし、マークするたびにサブセグメントがマークされているか否かを判断する)

#include 

using namespace std;

const int N = 100;
int n;
char ch[N];
map Time;

struct node
{
    char c[N];
    int len;
}code[N];

typedef struct tree
{
    int sum;
    struct tree* left;
    struct tree* right;
    char c;
}*Tree;

struct cmp
{
    bool operator()(const Tree x, const Tree y)
    {
        return x->sum > y->sum;
    }
};

int BuildHuffman()
{
    int sum = 0;// 
    priority_queue, cmp> que;

    for(int i = 1; i <= n; i++)
    {
        Tree treenode = (Tree)malloc(sizeof(struct tree));
        treenode->c = ch[i];
        treenode->left = NULL;
        treenode->right = NULL;
        treenode->sum = Time[ch[i]];
        que.push(treenode);
    }
    while(que.size() > 1)
    {
        Tree lchild = que.top();
        que.pop();
        Tree rchild = que.top();
        que.pop();
        Tree father = (Tree)malloc(sizeof(struct tree));
        father->left = lchild;
        father->right = rchild;
        father->sum = lchild->sum + rchild->sum;
        que.push(father);
    }

    Tree head = que.top();
    typedef pair P;
    queue
 q;
    q.push(P(head,0));
    while(!q.empty())// 
    {
        P p = q.front();
        q.pop();
        if(p.first->left)
            q.push(P(p.first->left, p.second+1));
        if(p.first->right)
            q.push(P(p.first->right, p.second+1));
        if(!p.first->left && !p.first->right)
            sum += Time[p.first->c]*p.second;
    }

    return sum;
}

int cmp1(const struct node x, const struct node y)
{
    return x.len < y.len;
}

bool Only()
{
    map mp;
    sort(code+1,code+1+n,cmp1);
    string s;
    for(int i = 1; i <= n; i++)
    {
        s.clear();
        for(int j = 0; j < code[i].len; j++)
        {
            s += code[i].c[j];
            if(mp[s])
                return 0;
        }
        mp[s] = 1;
    }
    return 1;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf(" %c", &ch[i]);//ch ， 
        scanf("%d", &Time[ch[i]]);// MAP （ ）
    }

    int Minmum = BuildHuffman();// 

    int m;
    scanf("%d", &m);
    while(m--)
    {
        int flag = 0;
        char c;
        int SumCost = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf(" %c %s", &c, code[i].c);
            code[i].len = strlen(code[i].c);
            SumCost += Time[c]*code[i].len;// 
        }

        if(SumCost > Minmum)
            printf("No
");
        else if(!Only())
            printf("No
");
        else
            printf("Yes
");
    }

    return 0;
}