let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

HEAP1 - Một chút về Huffman Tree

solution.md

Hình trên là cách cắt tối ưu cho input mẫu. Một cách cắt có thể được biểu diễn bởi cây với các nút lá là các số trong dãy A.

Từ cây biểu diễn như trên, ta có thể tính chi phí cắt như sau:

\[C = \sum A_i\times B_i\]

Với \(A_i\) là nút lá và \(B_i\) là bậc của nút đó. Ví dụ như trong cách cắt trên thì chi phí cắt là:

\[C = 4\times 1 + 3 \times 2 + 2 \times 3 + 1 \times 3 = 19\]

Ta sẽ xây dựng cây từ dưới lên đồng thời sử dụng tư tưởng tham lam, ta sẽ cho các số nhỏ hơn nằm ở lá sâu hơn. Từ đó xây dựng được thuật toán bên dưới:

Đầu tiên ta thêm tất cả các phần tử của dãy vào heap. Sau đó lặp trong khi heap có nhiều hơn 1 phần tử:

  • Lấy ra 2 phần tử nhỏ nhất \(a\) và \(b\) trong heap, cộng kết quả cho \(a + b\).
  • Thêm \(a + b\) vào heap với ý nghĩa là hai nút \(a\) và \(b\) sẽ có nút cha là \(a + b\).
main.cpp
Open in Github • Download 
#include <iostream>
#include <queue>
using namespace std;

#define LL long long
typedef priority_queue<LL, vector<LL>, greater<LL>> min_heap;

void query() {
    int n; cin >> n;
    min_heap heap;
    while (n--) {
        LL x; cin >> x;
        heap.push(x);
    }

    LL 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);
    }

    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) query();
    return 0;
}
Comments