solution

Đề bài: [Hệ điều hành Unix] Huffman: độ dài mã trung bình

Độ dài mã trung bình Huffman

Độ dài mã trung bình = (tổng số bit) / (tổng tần suất). Tổng số bit tính qua min-heap như bài tổng bit Huffman.

Nếu chỉ 1 ký hiệu, độ dài trung bình là 1.00.

Ví dụ

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

Input :
4
1 1 2 4
Output: 1.75

Định dạng đầu vào:
Dòng đầu n. Dòng sau gồm n tần suất nguyên dương.
Ràng buộc đầu vào:
1 ≤ n ≤ 10^5; 1 ≤ freq ≤ 10^9.
Định dạng đầu ra:
Độ dài mã trung bình, 2 chữ số thập phân.

Ví dụ:

Đầu vào:

4
1 1 2 4

Đầu ra:

1.75

Giải thích:

Tổng bit 14, tổng tần suất 8, độ dài trung bình 14/8 = 1.75.

Đang tải editor...