Hiểu bài toán

Bài toán cầu là một bài toán quy hoạch động kinh điển. Có N người muốn qua một cây cầu tối tăm chỉ có một chiếc đèn pin. Mỗi người có thời gian qua cầu khác nhau. Cầu chỉ chịu được tối đa 2 người cùng lúc. Khi 2 người qua cùng lúc, thời gian tính bằng người chậm hơn. Đèn pin phải được mang về để đưa người tiếp theo qua. Hãy tìm cách đưa tất cả mọi người qua cầu trong thời gian ít nhất.

Các cách tiếp cận

Cách Greedy (Lựa chọn ngẫu nhiên)

// Không khuyến khích, nhưng đơn giản nhất
// Luôn đưa 2 người nhanh nhất qua và người nhanh nhất quay lại
// Hoặc luôn đưa người nhanh nhất đưa từng người chậm nhất
// Code mẫu:
long long res = 0;
while (n > 1) {
    // Luôn cách này không tối ưu, chỉ minh họa Greedy
    res += t[0] + t[n-1]; // Người nhanh nhất đưa người chậm nhất
    n--; // Người chậm nhất đã qua, người nhanh nhất quay lại (trừ khi hết người)
    if (n == 1) break;
    res += t[0]; // Quay lại
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Cách này chỉ ưu tiên một hướng duy nhất: luôn dùng người nhanh nhất để đưa người chậm nhất. Tuy nhiên, có những trường hợp việc dùng 2 người nhanh nhất để đưa 2 người chậm nhất qua cùng lúc (và dùng người thứ 2 để mang đèn về) lại tiết kiệm thời gian hơn. Ví dụ: [1, 2, 5, 10]. Greedy sẽ là (1+10) + 1 + (1+5) = 18. Nhưng tối ưu là (1+2) + 1 + (5+10) + 2 = 17.

Cách Quy hoạch động / Chia để trị (Tối ưu hóa)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ifstream fin("bridge.inp");
    ofstream fout("bridge.out");

    int N;
    fin >> N;
    vector<int> t(N);
    for(int i = 0; i < N; i++) fin >> t[i];

    sort(t.begin(), t.end());

    long long res = 0;
    int n = N;

    while(n > 3) {
        // Phương án 1: Hai người nhanh nhất đưa hai người chậm nhất
        // A, B qua (thời gian B); A về (thời gian A); C, D qua (thời gian D); B về (thời gian B)
        // Tổng: t[1] + t[0] + t[n-1] + t[1]
        long long option1 = t[1] + t[0] + t[n-1] + t[1];

        // Phương án 2: Người nhanh nhất đưa từng người chậm nhất
        // A, D qua (thời gian D); A về (thời gian A); A, C qua (thời gian C); A về (thời gian A)
        // Tổng: t[n-1] + t[0] + t[n-2] + t[0]
        long long option2 = t[n-1] + t[0] + t[n-2] + t[0];

        res += min(option1, option2);
        n -= 2; // Đã đưa được 2 người cuối qua
    }

    if(n == 3) {
        res += t[0] + t[1] + t[2];
    } else if(n == 2) {
        res += t[1];
    } else if(n == 1) {
        res += t[0];
    }

    fout << res << "\n";
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Đây là phương pháp tối ưu (Greedy kết hợp Quy hoạch động). Chúng ta sắp xếp thời gian tăng dần. Khi còn nhiều người (>3), ta có 2 lựa chọn để đưa 2 người chậm nhất (t[n-1], t[n-2]) qua:

1. (1+2) -> 1 về -> (n-1 + n-2) -> 2 về. Chi phí: 2*t[1] + t[0] + t[n-1].
2. (1 + n-1) -> 1 về -> (1 + n-2) -> 1 về. Chi phí: 2*t[0] + t[n-1] + t[n-2]. Ta chọn phương án nhỏ hơn. Lặp lại cho đến khi còn <= 3 người.

• Nếu còn 3 người: A, B, C -> A, B qua (B), A về (A), A, C qua (C). Tổng: B + A + C.
• Nếu còn 2 người: A, B qua -> t[B].
• Nếu còn 1 người: A qua -> t[A].

Phân tích độ phức tạp

Bài học kinh nghiệm

• Luôn sắp xếp lại thời gian của mọi người trước khi tính toán.
• Bài toán có cấu trúc lặp lại (mỗi lần giải quyết 2 người chậm nhất), nên có thể dùng kỹ thuật quy hoạch động hoặc lặp lại công thức tính giá trị nhỏ nhất cho 2 người cuối.
• Có 2 trường hợp cơ bản để đưa 2 người chậm nhất qua: hoặc dùng 2 người nhanh nhất làm 'xe bus', hoặc dùng 1 người nhanh nhất làm 'xe bus'.

Lỗi thường gặp

• Quên mang đèn pin về (tính thời gian quay lại).
• Lỗi quá biên mảng khi truy cập t[N-1] khi N=1.
• Sử dụng biến số có kiểu dữ liệu quá nhỏ (ví dụ int) dẫn đến tràn số khi cộng dồn thời gian (nên dùng long long).