Pagini recente » Borderou de evaluare (job #2763227) | Cod sursa (job #2698296)
#include <fstream>
#include <vector>
using namespace std;
ifstream be("huffman.in");
ofstream ki("huffman.out");
const long long inf = 1LL * 1000000000 * 1000000000;
const int maxn=1000100;
struct node
{
long long freq;
long f[2];
}huff[2*maxn];
long lg[maxn],q[2][maxn];
long long b[maxn];
void print(long poz,long long cod,long level)
{
if(huff[poz].f[0])
{
print(huff[poz].f[0],2*cod,level+1);
print(huff[poz].f[1],cod*2+1,level+1);
return;
}
lg[poz]=level;
b[poz]=cod;
}
void huffman(long n)
{
long k=n;
long r[2],l[2];
l[0]=l[1]=1;
r[0]=n,r[1]=0;
long long sol=0,min;
long p;
while(l[0]+l[1]<=r[0]+r[1])
{
++k;
for(int j=0;j<2;j++)
{
p=0;
min=inf;
for(int i=0;i<2;i++)
{
if(huff[q[i][l[i]]].freq<min && l[i]<=r[i])
{
p=i;
min=huff[q[i][l[i]]].freq;
}
}
huff[k].f[j]=q[p][l[p]];
huff[k].freq+=huff[q[p][l[p]]].freq;
l[p]++;
}
sol+=huff[k].freq;
q[1][++r[1]]=k;
}
print(k,0,0);
ki<<sol<<endl;
}
int main()
{
long n;
be>>n;
/* vector<node>huff(2*n+100);
vector<long>lg(n+100);
vector<long long>b(n+100);
vector<vector<long> >q(2,vector<long>(n+100));*/
for(int i=1;i<=n;i++)
{
be>>huff[i].freq;
q[0][i]=i;
}
huffman(n);
for(int i=1;i<=n;i++)
{
ki<<lg[i]<<" "<<b[i]<<endl;
}
return 0;
}