Pagini recente » Cod sursa (job #2630491) | Cod sursa (job #1580787) | Cod sursa (job #1446782) | Cod sursa (job #1583461) | Cod sursa (job #1624910)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int nmax=1000001;
int k;
long long sol,tot;
struct nod
{
long long z;
int st,dr,lvl;
}arb[2*nmax];
queue<int> Q,H;
int unite(int a,int b)
{
arb[k].z=arb[a].z+arb[b].z;
sol+=arb[k].z;
arb[k].st=a;
arb[k].dr=b;
return k;
}
void dfs(int nod,int niv,long long cod)
{
if(arb[nod].st!=0)
{
dfs(arb[nod].st,niv+1,cod*2);
}
if(arb[nod].dr!=0)
{
dfs(arb[nod].dr,niv+1,cod*2+1);
}
if(!arb[nod].dr && !arb[nod].st)
{
arb[nod].lvl=niv;
arb[nod].z=cod;
}
}
int main()
{
freopen("huffman.in","r",stdin);
freopen("huffman.out","w",stdout);
int n,i,a,b,step1,step2;
scanf("%d",&n);
k=n+1;
for(i=1;i<=n;++i)
{
scanf("%lld",&arb[i].z);
Q.push(i);
}
sol=0;
while(1)
{
step1=0;step2=0;
if(Q.size()) step1=Q.front();
if(H.size()) step2=H.front();
if(step1==0) {a=step2;H.pop();}
else if(step2==0) {a=step1;Q.pop();}
else if(arb[step1].z<=arb[step2].z) {a=step1;Q.pop();}
else {a=step2;H.pop();}
step1=0;step2=0;
if(Q.size()) step1=Q.front();
if(H.size()) step2=H.front();
if(step1==0) {b=step2;H.pop();}
else if(step2==0) {b=step1;Q.pop();}
else if(arb[step1].z<=arb[step2].z) {b=step1;Q.pop();}
else {b=step2;H.pop();}
H.push(unite(a,b));k++;
if(Q.size()+H.size()<=1) break;
}
printf("%lld\n",sol);
dfs(H.front(),0,0);
for(i=1;i<=n;++i)
{
printf("%d %lld\n",arb[i].lvl,arb[i].z);
}
}