Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Hệ điều hành Unix] Huffman: tổng số bit

    Độ dài mã Huffman (tổng số bit)

    Mã hóa Huffman gán mã ngắn cho ký hiệu xuất hiện nhiều. Tổng số bit của thông điệp nén bằng tổng freq[i] * len(code[i]).

    Một cách tính nhanh: dùng min-heap, lặp lấy 2 tần suất nhỏ nhất a, b, cộng a+b vào tổng và đẩy a+b trở lại heap. Tổng các lần gộp chính là tổng số bit.

    Nếu chỉ có 1 ký hiệu, mã dài 1 bit nên tổng bit = tần suất của nó.

    Ví dụ

    Tần suất [1, 1, 2, 4] → tổng bit = 14.

    Input :
4
1 1 2 4
Output: 14
    • Định dạng đầu vào:

      Dòng đầu là n (số ký hiệu). Dòng sau gồm n số nguyên dương là tần suất.

    • Ràng buộc đầu vào:

      1 ≤ n ≤ 10^5; 1 ≤ freq ≤ 10^9.

    • Định dạng đầu ra:

      Tổng số bit của thông điệp sau mã hóa Huffman.

    Ví dụ:

    Đầu vào:

    4
1 1 2 4

    Đầu ra:

    14

    Giải thích:

    Gộp 1+1=2 (tổng 2), 2+2=4 (tổng 6), 4+4=8 (tổng 14). Tổng số bit là 14.

    Đang tải editor...