# Cod sursa(job #2792333)

Utilizator Data 1 noiembrie 2021 14:41:15 Coduri Huffman 50 cpp-64 done Arhiva educationala 1.43 kb
``````#include <bits/stdc++.h>
#define N -1
using namespace std;

ifstream fin("huffman.in");
ofstream fout("huffman.out");
const int NMAX = 1e6+100;
int n;
long long sum;

struct nod
{
long long val, dec;
int left, right, ad;
}w[2*NMAX];

///0 pe stanga, 1 pe dreapta
void dfs(int nod, int ad, long long val)
{
if(nod > 0)
{
w[nod].dec = val;
w[nod].ad = ad;
if(nod > n)
sum += w[nod].val;
dfs(w[nod].left, ad+1, val<<1);
dfs(w[nod].right, ad+1, (val+1)<<1);
}
}

void huffman()
{
int i, j, stop, first, second;
i = 1;
j = n+2;
stop = n+1;

while(i <= n)
{
if(j <= stop && w[j].val < w[i].val)
first = j, ++j;
else first = i, ++i;

if(j <= stop && w[j].val < w[i].val)
second = j, ++j;
else second = i, ++i;

w[++stop].val = w[first].val + w[second].val;
w[stop].left = first;
w[stop].right = second;
}

while(j + 1 <= stop)
{
w[++stop].val = w[j].val + w[j+1].val;
w[stop].left = j;
w[stop].right = j+1;
j += 2;
}
dfs(stop, 0ll, 0ll);
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> w[i].val;

huffman();

fout << sum << '\n';

for(int i = 1; i <= n; ++i)
fout << w[i].ad << ' ' << w[i].dec << '\n';
return 0;
}
``````