# Cod sursa(job #2207175)

Utilizator Data 25 mai 2018 00:22:59 Coduri Huffman 100 cpp done Arhiva educationala 2.57 kb
``````//#include <iostream>
//#include <fstream>
#include <stdio.h>
#include <queue>
#include <string>
#define NMAX 1000005

using namespace std;

//ifstream f("huffman.in");
//ofstream g("huffman.out");

//queue< long > Q, newQ;
int Q[NMAX], newQ[NMAX], sizeQ = 0, sizeNewQ = 0, startQ = 0, startNewQ = 0;

struct Node
{
long long value;
long next[2];
}node[2*NMAX];

int n, k, root, level[2 * NMAX];
long long cod[2 * NMAX], lg;

void calcLevel(int k, int nivel, long long c)
{
level[k] = nivel;
cod[k] = c;
if (node[k].next[0] != 0)
{
calcLevel(node[k].next[0], nivel + 1, 2 * c);
calcLevel(node[k].next[1], nivel + 1, 2 * c + 1);
}
}

void solve()
{
k = n;

//while (Q.size() + newQ.size() >= 2)
while (sizeQ + sizeNewQ - startQ - startNewQ >= 2)
{
long x1, x2;

//if (!newQ.empty() && (Q.empty() || node[Q.front()].value >  node[newQ.front()].value))
if (sizeNewQ > startNewQ && (sizeQ <= startQ || node[Q[startQ]].value > node[newQ[startNewQ]].value))
{
//x1 = newQ.front();
x1 = newQ[startNewQ++];
//newQ.pop();
}
else
{
//x1 = Q.front();
//Q.pop();
x1 = Q[startQ++];
}

//if (!newQ.empty() && (Q.empty() || node[Q.front()].value >  node[newQ.front()].value))
if (sizeNewQ > startNewQ && (sizeQ <= startQ || node[Q[startQ]].value > node[newQ[startNewQ]].value))
{
x2 = newQ[startNewQ++];
}
else
{
x2 = Q[startQ++];
}

k++;
node[k].value = node[x1].value + node[x2].value;
lg += node[k].value;
node[k].next[0] = x1;
node[k].next[1] = x2;
//newQ.push(k);
newQ[sizeNewQ++] = k;
}
root = k;
}

{
//f >> n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
//f >> node[i].value;
int x;
scanf("%d", &x);
node[i].value = x;
node[i].next[0] = node[i].next[1] = 0;
//Q.push(i);
Q[i] = i;
}
startQ = 1;
sizeQ = n + 1;
startNewQ = 1;
sizeNewQ = 1;
}

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

//long long sum = 0;
//for (int i = 1; i <= n; i++)
//sum += node[i].value * level[i];
//g << lg <<'\n';
printf("%lld\n", lg);

for (int i = 1; i <= n; i++)
//g << level[i] << ' ' << cod[i] << '\n';
printf("%d %lld\n", level[i], cod[i]);
return 0;
}``````