Editorial for Một chút về Huffman Tree


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      maxn=50050;
var n,nh,test,it,i,x:longint; re:real;
    h:array[1..maxn] of longint;

procedure update(x:longint);
var u,v:longint;
begin
     inc(nh); v:=nh; u:=v shr 1;
     while (u>0) and (h[u]>x) do
     begin
          h[v]:=h[u];
          v:=u;
          u:=v shr 1;
     end;
     h[v]:=x;
end;

function pop:longint;
var u,v,x:longint;
begin
     pop:=h[1];
     x:=h[nh]; dec(nh);
     u:=1; v:=2;
     while v<=nh do
     begin
          if (v<nh) and (h[v+1]<h[v]) then inc(v);
          if h[v]>=x then break;
          h[u]:=h[v];
          u:=v; v:=u shl 1;
     end;
     h[u]:=x;
end;

begin
     assign(input,fi); reset(input);
     read(test);
     for it:=1 to test do
     begin
          read(n);
          nh:=0;
          for i:=1 to n do
          begin
               read(x);
               update(x);
          end;
          re:=0;
          for i:=1 to n-1 do
          begin
               x:=pop+pop;
               re:=re+x;
               update(x);
          end;
          writeln(re:0:0);
     end;
     close(input);
end.

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define long long long
using namespace std;
int n, t;

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        priority_queue<long, vector<long>, greater<long> > heap;
        int v;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &v);
            heap.push(v);
        }
        long res = 0;
        while (heap.size() > 1) {
            int a = heap.top(); heap.pop();
            int b = heap.top(); heap.pop();
            res += a + b;
            heap.push(a + b);
        }
        printf("%lld\n", res);
    }
    return 0;
}

Code mẫu của RR

var
  u,v,hsize,test,n,i:longint;
  h:array[1..20111] of longint;
  res:int64;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure down(i:longint);
    var
      j:longint;
    begin
      j:=i shl 1;
      while (j<=hsize) do
        begin
          if (j<hsize) and (h[j+1]<h[j]) then inc(j);
          if h[j]<h[i] then
            begin
              swap(h[i],h[j]);
              i:=j; j:=i shl 1;
            end
          else exit;
        end;
    end;

procedure up(i:longint);
    var
      j:longint;
    begin
      j:=i shr 1;
      while (i>1) and (h[i]<h[j]) do
        begin
          swap(h[i],h[j]);
          i:=j; j:=i shr 1;
        end;
    end;

procedure push(u:longint);
    begin
      inc(hsize); h[hsize]:=u;
      up(hsize);
    end;

procedure pop(var u:longint);
    begin
      u:=h[1];
      swap(h[1],h[hsize]);
      dec(hsize); down(1);
    end;

begin
  read(test);
  for test:=1 to test do
    begin
      read(n); for i:=1 to n do begin read(u); push(u); end;
      res:=0;
      while hsize>1 do
        begin
          pop(u); pop(v);
          res:=res+u+v;
          push(u+v);
        end;

      pop(u);
      writeln(res);
    end;
end.

Code mẫu của hieult

#include<iostream>
#include<vector>
//#include<conio.h>

using namespace  std;

vector<long long> a;
long n;
long long kq,tong;

int xuli()
{
 long i,j,x,y;
 make_heap(a.begin(),a.end());
 kq = 0;
 for (i=1;i<=n-1;i++)
   {
     x = a[0];
     pop_heap(a.begin(),a.end());
     a.pop_back();
     y = a[0];
     pop_heap(a.begin(),a.end());
     a.pop_back();
     kq = kq + x+y;
     a.push_back(x+y);
     push_heap(a.begin(),a.end());
   }  
}


int main()
{
 long x,test,i,j;
 cin>>test;
 for (i=1;i<=test;i++)
   {
    cin>>n;
    for (j=1;j<=n;j++)
      {
        cin>>x;
        x = -x;
        a.push_back(x);
      } 
    xuli();
    a.pop_back();
    cout<<-kq<<endl;  
   }
 //getch();  
}

Code mẫu của khuc_tuan

from heapq import *
for z in range(input()):
    n=input()
    h=[int(x) for x in raw_input().split()]
    heapify(h)
    r=0
    for i in range(n-1):
        t=heappop(h)
        t+=heappop(h)
        r+=t
        heappush(h,t)
    print r

Comments

Please read the guidelines before commenting.


There are no comments at the moment.