Hiểu bài toán

Đề bài cho biết tổng số diễn viên ~n~, số diễn viên cao ~a~, số diễn viên mắt xanh ~b~, và số diễn viên tóc vàng ~c~. Đạo diễn cần chọn diễn viên cho vai chính phải thỏa mãn cả 3 điều kiện: cao, mắt xanh và tóc vàng. Với 2 loại truy vấn: ~k=1~ yêu cầu tìm số lượng diễn viên tối thiểu có thể chọn được, ~k=2~ yêu cầu tìm số lượng diễn viên tối đa có thể chọn được.

Phân tích:

• Để chọn được tối đa, ta chỉ có thể chọn số lượng diễn viên ít nhất trong 3 nhóm đặc điểm (vì một diễn viên phải có đủ cả 3 đặc điểm). Vậy số lượng tối đa là min(a, b, c).
• Để chọn được tối thiểu, ta cần xét khả năng không chọn được ai (số lượng bằng 0). Điều này xảy ra khi các nhóm đặc điểm quá ít ỏi hoặc phân bổ không đều đến mức không thể giao nhau. Dựa trên quy tắc loại trừ (nguyên lý tổ hợp), số lượng tối thiểu đảm bảo là max(0, a + b + c - 2*n).

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

Cách Phân tích tập hợp (Tối ưu)

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

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

    int k, n, a, b, c;
    cin >> k >> n >> a >> b >> c;

    int ans;
    if (k == 1) {
        // Tối thiểu: Sử dụng công thức a + b + c - 2*n
        // Nếu âm thì trả về 0
        ans = max(0, a + b + c - 2 * n);
    } else {
        // Tối đa: Giao của 3 tập hợp
        ans = min({a, b, c});
    }
    cout << ans;
    return 0;
}

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

Đây là phương pháp hiệu quả nhất dựa trên toán học.

• Với k=2 (tối đa): Số lượng diễn viên có đủ 3 đặc điểm không thể vượt quá số lượng diễn viên trong bất kỳ nhóm nào. Do đó, kết quả là giá trị nhỏ nhất trong 3 số a, b, c.
• Với k=1 (tối thiểu): Ta cần tìm số lượng tối thiểu bị trùng lặp. Giả sử tổng số người không có đặc điểm cao là n - a, không có mắt xanh là n - b, không có tóc vàng là n - c. Theo nguyên lý bù trừ, số người có thể không có ít nhất một đặc điểm (tức là không thể casting) tối đa là (n - a) + (n - b) + (n - c) = 3n - (a + b + c). Số người bị loại này không được phép vượt quá tổng số người là n. Nếu 3n - (a + b + c) > n, tức là 2n > a + b + c, thì có người không bị loại (tức là có thể casting). Số người tối thiểu phải có đủ đặc điểm là a + b + c - 2n. Nếu giá trị này âm, tức là có thể không có ai đủ cả 3 đặc điểm (kết quả là 0).

Cách Quy hoạch động/Khảo sát

// Chỉ mang tính tham khảo, logic chính là công thức ở trên
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int k, n, a, b, c;
    cin >> k >> n >> a >> b >> c;

    if (k == 1) {
        int min_cast = max(0, a + b + c - 2 * n);
        cout << min_cast << "\n";
    } else if (k == 2) {
        int max_cast = min({a, b, c});
        cout << max_cast << "\n";
    }

    return 0;
}

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

Đây là cách tiếp cận trực quan.

• Tối đa: Chọn số lượng ít nhất trong 3 nhóm (min(a, min(b, c))).
• Tối thiểu: Dùng hàm max để xử lý trường hợp âm. Logic đằng sau là đạo lý '3 người cùng vác một cây gỗ': tổng số vai trò cần lấp đầy là a+b+c, nhưng mỗi diễn viên có thể đảm nhận tối đa 2 vai trò (vai còn lại là vai 'không có đặc điểm đó'). Do đó, nếu a+b+c > 2n, ta chắc chắn có người phải nhận cả 3 vai (tức có đặc điểm đầy đủ).

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

Bài học kinh nghiệm

• Bài toán tối đa hóa số lượng casting chính là bài toán tìm giao của 3 tập hợp (diễn viên cao, mắt xanh, tóc vàng).
• Bài toán tối thiểu hóa số lượng casting dựa trên nguyên lý bù trừ: a + b + c - 2*n (nếu dương) hoặc 0 (nếu âm hoặc zero).

Lỗi thường gặp

• Quên xử lý trường hợp kết quả âm đối với bài toán tìm số lượng tối thiểu (phải dùng max(0, ...)).
• Sử dụng các biến có kiểu dữ liệu quá nhỏ (ví dụ: int) nếu dữ liệu đầu vào lớn, nhưng trong bài này n <= 10000 nên int là đủ (tối đa ~3*10^4).
• Đối với k=2, nhầm lẫn giữa min(a, b, c) và các phép toán khác như a+b+c - ...