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.
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