霍夫曼编码解码

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, N;
string s[1005];

struct node
{
	int id;
	int w;
	node *l, *r;
	bool operator <(const node &x) const{
		return w == x.w ? id > x.id : w > x.w;
	}
}a[1005];

priority_queue<node> q;

void dfs(node *t, int flag, string str){
	if(t == NULL) return ;
	if(flag == 1){
		str += '1';
		s[t->id] = str;
	}else if(flag == 0){
		str += '0';
		s[t->id] = str;
	}
	if(t->l != NULL){
		dfs(t->l, 0, str);
	}
	if(t->r != NULL){
		dfs(t->r, 1, str);
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	N = n;
	for (int i = 1; i <= n; i++){
		scanf("%d", &a[i].w);
		a[i].id = i;
		a[i].l = NULL, a[i].r = NULL;
		q.push(a[i]);
	}
	node b[1005], t1[1005], t2[1005];
	int cnt = 0;
	while(q.size() != 1){
		t1[cnt] = q.top();
		q.pop();
		t2[cnt] = q.top();
		q.pop();
		b[cnt].w = t1[cnt].w + t2[cnt].w;
		b[cnt].id = ++n;
		b[cnt].l = &t1[cnt], b[cnt].r = &t2[cnt];
		q.push(b[cnt++]);
	}
	node t = q.top();
	dfs(&t, -1, "");
	for (int i = 1; i <= N; i++){
		cout << (char)(i + 'A' - 1) << " " << s[i] << endl;
	}

	return 0;
}
/**/
/*
10
19 18 16 14 12 8 6 4 2 1
*/