站外题求助,蒟蒻一头雾水 qaq
题面
有 n 个单词,编号从 1∼n。第 i 个单词的出现的次数为 ai。
某人对这些单词进行了二进制编码,第 i 个单词编码后的二进制数用一个字符串 si 表示。
请你判断此人的编码是不是这个出现次数下合法的哈夫曼编码。
如果是,输出 Yes,并计算出按照这个编码的文章总长度(二进制位数)。
否则,输出 No,并给出一组满足要求的哈夫曼编码。
注意:本题中只要保证了在该二进制编码下,文章总长度能达到最短;且任意一个编码都不是其他编码的前缀;就认为是一个合法的哈夫曼编码。
输入格式
第一行是 n。
第二行为空格隔开的 a1∼an。
接下来 n 行,第 i 行为 si。
输出格式
按题目要求输出:
如果输入的是哈夫曼编码,输出两行:
第一行为 Yes;
第二行为这个编码下的文章总长度。
如果输入的不是哈夫曼编码,输出 n+1 行:
第一行为 No;
接下来 n 行,第 i 行为第 i 个单词对应的哈夫曼编码。
如果有多种方案,输出任意一种即可。