Pagini recente » Cod sursa (job #1049595) | Cod sursa (job #928632) | Cod sursa (job #1933680) | Cod sursa (job #817112) | Cod sursa (job #430134)
Cod sursa(job #430134)
#include<stdio.h>
#define Nmax 1000010
struct Arb { int key; long long cost; Arb *st,*dr;} *A[Nmax<<1];
int n,Q1[Nmax],Q2[Nmax],i,L[Nmax],R,nod1,nod2,p,u,cst;
long long Sum,Cod[Nmax];
void dfs ( Arb *nod, long long cod, int mSize)
{
if(nod->st==NULL)
{
L[nod->key]=mSize;
Cod[nod->key]=cod;
return ;
}
dfs(nod->st,cod<<1,mSize+1);
dfs(nod->dr,(cod<<1)+1,mSize+1);
}
void add()
{
R++;
A[R]=new Arb;
A[R]->cost = A[nod1]->cost + A[nod2]->cost;
A[R]->st=A[nod1];
A[R]->dr=A[nod2];
}
int main()
{
freopen("huffman.in","r",stdin);
freopen("huffman.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&cst);
Q1[i]=i;
A[i] = new Arb;
A[i]->key=i;
A[i]->cost=cst;
A[i]->st=A[i]->dr=NULL;
}
if(n==1) {printf("0\n1 0"); return 0;}
R=n;
nod1=1; nod2=2;
add();
i=3; Q2[1]=R; p=u=1;
while(i<=n)
{
nod1=Q1[i];
nod2=Q2[p];
if(i+1<=n && A[Q1[i+1]]->cost < A[nod2]->cost)
{
nod2=Q1[i+1];
i+=2;
}
else if(p+1<=u && A[Q2[p+1]]->cost < A[nod1]->cost)
{
nod1=Q2[p+1];
p+=2;
}
else i++,p++;
add();
Q2[++u]=R;
}
while(p!=u)
{
nod1=Q2[p];
nod2=Q2[p+1];
p+=2;
add();
Q2[++u]=R;
}
dfs(A[R],0,0);
for(i=1;i<=n;i++)
Sum+=L[i]*A[i]->cost;
printf("%lld\n",Sum);
for(i=1;i<=n;i++)
printf("%d %lld\n",L[i],Cod[i]);
return 0;
}