算法5-16 对二进制字符串解码

输入样例：

5
a 4
b 3
c 2
w 1
z 1
100001110101101101100111

输出样例：

baaacabwbzc

ac代码：

 

#include<iostream>
#include<queue>
#include<map>
using namespace std;
const int N=10010;
int idx;
int a[N][2];
char b[N];
map<string,char>mp;
struct node{int num,id;bool operator<(const node&n1)const{return n1.num==num?n1.id>id:n1.num<num;}};
void dfs(int u,string str){if(!a[u][0]){mp[str]=b[u]; return;}dfs(a[u][0],str+'0');dfs(a[u][1],str+'1');
}
priority_queue<node>pq;
int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){getchar();char c; scanf("%c",&c);int num; scanf("%d",&num);b[++idx]=c;pq.push({num,idx});}for(int i=1;i<n;i++){node tmp0=pq.top(); pq.pop();node tmp1=pq.top(); pq.pop();a[++idx][0]=tmp0.id;a[idx][1]=tmp1.id;pq.push({tmp0.num+tmp1.num,idx});}string str="";dfs(idx,str);string res; cin>>res;// for(map<string,char>::iterator it=mp.begin();it!=mp.end();it++){//     cout << "Key: " << it->first << ", ";//     // 访问值//     cout << "Value: " << it->second << endl;// }int l=0;for(int i=1;i<=res.size();i++){string s=res.substr(l,i-l);if(mp.find(s)!=mp.end()){//  cout<<s<<endl;printf("%c",mp[s]);l=i;}}return 0;
}

不知道上述这样写会不会很憨，思路：

构建哈夫曼树，把每个字母的编码求出，然后对最后的字符串进行匹配。