# Cod sursa(job #2793745)

Utilizator Data 3 noiembrie 2021 22:39:17 Coduri Huffman 100 cpp-64 done Arhiva educationala 1.73 kb
``````#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

const int NMAX = 1e6;

int n;
long long lungime_totala;
long long arb[2 * NMAX + 5];
int dad[2 * NMAX + 5];
bool tip[2 * NMAX + 5];

queue<int> frunze;
queue<int> noduri;

void citire() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld", &arb[i]);
frunze.push(i);
}
}

int pop_min(queue<int> &q1, queue<int> &q2) {
if(!q1.empty() && (q2.empty() || arb[q1.front()] <= arb[q2.front()])) {
int poz_min = q1.front();
q1.pop();
return poz_min;
}
else {
int poz_min = q2.front();
q2.pop();
return poz_min;
}
}

void build_tree() {
lungime_totala = 0;
int last_node = n;

while(frunze.size() + noduri.size() > 1) {
int poz_min1 = pop_min(frunze, noduri);
int poz_min2 = pop_min(frunze, noduri);

arb[ ++last_node ] = arb[poz_min1] + arb[poz_min2];
lungime_totala += arb[last_node];
tip[poz_min1] = false;
tip[poz_min2] = true;

noduri.push(last_node);
}
}

void print_node(int poz) {
int lungime = 0;
long long cod = 0;
long long p2 = 1;

while(poz < 2 * n - 1) {
lungime++;
cod += p2 * tip[poz];
p2 <<= 1;
}

printf("%d %lld\n", lungime, cod);
}

void afisare() {
printf("%lld\n", lungime_totala);
for(int i = 1; i <= n; i++)
print_node(i);
}

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

citire();
build_tree();
afisare();

return 0;
}``````