Hiểu bài toán

Bài toán yêu cầu tìm chi phí thấp nhất để mua chính xác n vé xe buýt. Có hai cách mua vé: mua lẻ từng vé với giá a VNĐ/vé, hoặc mua theo gói m vé với giá b VNĐ/gói. Với mỗi test case gồm n, m, a, b, ta cần tính toán và chọn ra phương án tối ưu nhất (mua hoàn toàn vé lẻ, mua kết hợp gói và vé lẻ, hoặc mua thừa gói).

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

Cách Tối ưu bằng công thức

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, a, b;
        cin >> n >> m >> a >> b;

        // Phương án 1: Mua tất cả vé lẻ
        int cost1 = n * a;

        // Phương án 2: Mua tối đa các gói, còn lại mua lẻ
        int cost2 = (n / m) * b + (n % m) * a;

        // Phương án 3: Mua tròn gói (mua thêm 1 gói để có đủ vé)
        int cost3 = ((n / m) + 1) * b;

        cout << min({cost1, cost2, cost3}) << "\n";
    }
    return 0;
}

• Time Complexity: O(1) mỗi test case
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp và hiệu quả nhất. Ta chỉ cần xem xét 3 trường hợp cơ bản:

1. Mua tất cả vé lẻ: Chi phí = n * a.
2. Mua số gói nguyên (n/m) và vé lẻ (n%m): Chi phí = (n/m)b + (n%m)a.
3. Mua tròn gói (vì đôi khi mua thêm một gói còn rẻ hơn mua vé lẻ): Chi phí = ((n/m)+1)*b. Sau đó lấy giá trị nhỏ nhất trong 3 trường hợp này.

Cách Brute Force (Duyệt các khả năng)

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, a, b;
        cin >> n >> m >> a >> b;

        int min_cost = n * a; // Bat dau bang mua le het

        // Duyet so goi tu 0 den n/m + 1
        for (int k = 0; k <= n/m + 1; ++k) {
            int tickets_got = k * m;
            int cost = k * b;
            if (tickets_got < n) {
                cost += (n - tickets_got) * a;
            }
            if (cost < min_cost) min_cost = cost;
        }

        cout << min_cost << "\n";
    }
    return 0;
}

• Time Complexity: O(n/m) ~ O(n)
• Space Complexity: O(1)

Cách này duyệt qua tất cả số lượng gói có thể mua từ 0 đến số gói cần thiết (có thể dư một chút). Với mỗi số lượng gói k, ta tính chi phí mua k gói và vé lẻ phần còn lại. Dù chậm hơn cách công thức nhưng vẫn chấp nhận được với giới hạn n <= 1000.

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

Bài học kinh nghiệm

• Luôn có 3 phương án chính cần so sánh: Mua lẻ hết, Mua gói + lẻ, và Mua thừa gói.
• Kiểm tra kỹ các số nguyên (integer division) khi tính số gói và số vé lẻ.

Lỗi thường gặp

• Quên so sánh với phương án mua vé lẻ hoàn toàn (cost1).
• Sai công thức khi tính số vé còn lại sau khi mua gói (dùng phép chia số nguyên).
• Trường hợp n chia hết cho m, phương án 2 và 3 có thể chênh lệch.