Hiểu bài toán

Bài toán yêu cầu tìm tổng số lượng bóng tối đa có thể nhặt được dựa trên 4 số nguyên dương R, G, B, Y (tượng trưng cho số lượng bóng của từng màu) và một số nguyên K. Điều kiện là chỉ được phép có tối đa 1 quả bóng có giá trị >= K. Nếu không có quả bóng nào >= K thì không thể nhặt bóng nào (tổng = 0).

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

Cách Mô phỏng theo từng bước

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

int main() {
    int lb = 4;
    long long ans;
    bool check = false;
    long long arr[4];
    for (int i = 0; i < 4; i++) {
        long long a;
        cin >> a;
        arr[i] = a;
    }
    long long k;
    cin >> k;
    long long sum = 0;
    for (int j = 0; j < 4; j++) {
        if (arr[j] >= k && !check) {
            arr[j] = k;
            sum = sum + arr[j];
            check = true;
        } else if (arr[j] >= k) {
            arr[j] = k - 1;
            sum = sum + arr[j];
        } else {
            sum = sum + arr[j];
        }
    }
    if (check) {
        cout << sum;
    } else {
        cout << 0;
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này sử dụng một mảng để lưu trữ 4 giá trị R, G, B, Y. Nó duyệt qua từng phần tử, sử dụng một biến cờ hiệu check để đánh dấu xem đã gặp giá trị >= K hay chưa. Nếu là giá trị >= K đầu tiên, nó được giữ nguyên (hoặc gán bằng K). Các giá trị >= K tiếp theo bị giảm xuống K-1. Cuối cùng, nếu không có giá trị >= K nào (check vẫn false), tổng trả về là 0.

Cách Công thức toán học tối ưu

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long R, G, B, Y, K;
    cin >> R >> G >> B >> Y >> K;

    if (R < K && G < K && B < K && Y < K) {
        cout << 0 << "\n";
        return 0;
    }

    long long ans = min(R, K - 1) + min(G, K - 1) + min(B, K - 1) + min(Y, K - 1) + 1;
    cout << ans << "\n";
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này dựa trên quan sát toán học. Để tối đa hóa tổng số bóng:

1. Nếu không có quả nào >= K, tổng là 0.
2. Ngược lại, ta chọn một quả bóng >= K để cộng vào tổng (giá trị đóng góp tối đa là K).
3. Đối với các quả còn lại, ta chỉ có thể lấy tối đa K-1 quả mỗi màu (vì chỉ được phép có 1 quả >= K). Do đó, tổng = min(R, K-1) + min(G, K-1) + min(B, K-1) + min(Y, K-1) + 1. Công thức này tính toán trực tiếp kết quả mà không cần duyệt.

Cách Tối ưu hóa Logic

#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll solve(ll r, ll g, ll b, ll y, ll k) {
    ll res = 0;
    if (max(max(r, g), max(b, y)) < k)
        return 0;
    res += min(r, k - 1);
    res += min(g, k - 1);
    res += min(b, k - 1);
    res += min(y, k - 1);
    return res + 1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll r, g, b, y, k;
    cin >> r >> g >> b >> y >> k;
    cout << solve(r, g, b, y, k);
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là phiên bản được cấu trúc hóa của cách tiếp cận công thức. Hàm solve kiểm tra điều kiện đầu vào (giá trị lớn nhất có >= K không). Nếu có, nó tính toán tổng tương tự như Approach 2. Đây là cách tiếp cận được khuyến khích vì tính rõ ràng và xử lý lỗi (kiểu dữ liệu long long, tối ưu I/O).

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

Bài học kinh nghiệm

• Vấn đề có thể được giảm về bài toán tìm tổng số lượng bóng tối đa sao cho chỉ có tối đa 1 biến có giá trị >= K.
• Giá trị tối đa của một biến có thể đạt được nếu nó không phải là biến duy nhất >= K là K-1.
• Nếu không có biến nào >= K, kết quả là 0.

Lỗi thường gặp

• Quên kiểm tra trường hợp không có biến nào >= K (kết quả phải là 0).
• Sử dụng sai kiểu dữ liệu (ví dụ: int thay vì long long)导致 overflow.
• Viết lặp lại logic phức tạp thay vì dùng công thức tối ưu.