Bài toán: Tấm gỗ của Rui Rui

Bối cảnh bài toán:

Rui Rui muốn tự tay sửa lại hàng rào quanh một khu nhỏ của mình.

Mô tả bài toán:

Anh ấy đã đo đạc hàng rào và phát hiện ra mình cần n tấm gỗ, mỗi tấm có độ dài là số nguyên li. Vì vậy, anh ấy đã mua một tấm gỗ đủ dài, độ dài bằng tổng độ dài của n tấm gỗ cần thiết, và quyết định cắt tấm gỗ này thành n tấm gỗ cần thiết (Rui Rui không tạo ra mùn gỗ khi cắt, không cần xem xét độ hao hụt khi cắt).

Rui Rui sử dụng một cách cắt đặc biệt khi cắt một tấm gỗ độ dài thành hai tấm, anh ấy cần tiêu tốn đơn vị năng lượng bằng độ dài của tấm gỗ ban đầu. Rui Rui có nguồn năng lượng vô tận, nhưng hiện nay đề cao tiết kiệm năng lượng, vì vậy làm gương, anh ấy quyết định tiết kiệm năng lượng tối đa. Rõ ràng, tổng cộng cần cắt (n-1) lần, vấn đề là, mỗi lần nên cắt như thế nào? Hãy lập trình để tính tổng năng lượng tiêu tụ tối thiểu.

Định dạng đầu vào:

Dòng đầu tiên là số nguyên n, biểu thị số lượng tấm gỗ cần thiết.

Từ dòng thứ 2 đến dòng (n+1), mỗi dòng chứa một số nguyên, dòng thứ (i+1) chứa số nguyên li biểu thị độ dài của tấm gỗ thứ i.

Định dạng đầu ra:

Một số nguyên, biểu thị tổng năng lượng tiêu thụ tối thiểu.

Ví dụ đầu vào/đầu ra #1

Đầu vào #1:

3
8
5
8

Đầu ra #1:

34

Giải thích ví dụ 1:

Cắt tấm gỗ độ dài 21 thành hai tấm: một tấm 8 và một tấm 13, tiêu tốn 21 đơn vị năng lượng. Sau đó cắt tấm gỗ 13 thành hai tấm: 5 và 8, tiêu tốn 13 đơn vị năng lượng. Tổng cộng tiêu tốn 34 đơn vị năng lượng, là phương án tiêu tốn năng lượng ít nhất.

Phạm vi dữ liệu:

- Với 100% dữ liệu, đảm bảo 1 ≤ n ≤ 2×10^4, 1 ≤ li ≤ 5×10^4.

Giải pháp bằng C++

Bài toán này có thể giải bằng thuật toán Huffman, trong đó chúng ta liên tục kết hợp hai tấm gỗ nhỏ nhất để tối thiểu hóa năng lượng tiêu tụ.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

// So sánh để tạo hàng đợi ưu tiên (min-heap)
struct SoSanh {
    bool operator()(ll a, ll b) {
        return a > b;
    }
};

int main() {
    ll tongNangLuong = 0;
    int soLuongGia;
    cin >> soLuongGia;
    
    // Tạo hàng đợi ưu tiên (min-heap)
    priority_queue<ll, vector<ll>, SoSanh> hangDoiGia;
    
    // Đọc dữ liệu vào hàng đợi
    for(int i = 0; i < soLuongGia; i++) {
        ll doDai;
        cin >> doDai;
        hangDoiGia.push(doDai);
    }
    
    // Thực hiện thuật toán Huffman
    for(int i = 1; i < soLuongGia; i++) {
        // Lấy hai tấm gỗ nhỏ nhất
        ll nhoNhat1 = hangDoiGia.top();
        hangDoiGia.pop();
        
        ll nhoNhat2 = hangDoiGia.top();
        hangDoiGia.pop();
        
        // Tính năng lượng tiêu tụ khi ghép hai tấm gỗ
        ll nangLuongHienTai = nhoNhat1 + nhoNhat2;
        tongNangLuong += nangLuongHienTai;
        
        // Đặt tấm gỗ mới đã ghép vào hàng đợi
        hangDoiGia.push(nangLuongHienTai);
    }
    
    // In kết quả
    cout << tongNangLuong << endl;
    
    return 0;
}

Giải thích thuật toán:

• Chúng ta sử dụng hàng đợi ưu tiên (min-heap) để luôn có thể truy cập nhanh vào hai tấm gỗ nhỏ nhất.
• Tại mỗi bước, chúng ta lấy hai tấm gỗ nhỏ nhất, ghép chúng lại với nhau, và cộng thêm năng lượng tiêu tụ (tổng độ dài của hai tấm gỗ) vào kết quả.
• Tấm gỗ mới sau khi ghép được đưa trở lại hàng đợi để tham gia vào các bước tiếp theo.
• Quá trình này lặp lại cho đến khi chỉ còn một tấm gỗ duy nhất trong hàng đợi.