Hiểu bài toán

Cho ~n~ gian hàng xếp thành hàng, trong đó có ~k~ gian hàng đã được thuê (không biết vị trí cụ thể). Yugi muốn chọn một gian hàng trống sao cho nó có ít nhất một gian hàng kề bên (trái hoặc phải) đã được thuê. Hãy tìm số lượng gian hàng Yugi có thể chọn được ít nhất và nhiều nhất trong tất cả các cách sắp xếp ~k~ gian hàng đã thuê.

Phân tích:

• Nếu ~k = 0~ (không có gian hàng nào thuê), Yugi không thể chọn gian hàng nào vì không có gian hàng kề bên đã thuê. Kết quả là 0 0.
• Nếu ~k = n~ (tất cả đều thuê), không còn gian hàng trống. Kết quả là 0 0.
• Nếu ~k > 0~ và ~k < n~:
  • Tối thiểu: Dù sắp xếp thế nào, Yugi luôn có ít nhất 1 lựa chọn. Ví dụ, nếu đặt ~k~ gian hàng đã thuê thành 1 khối liền nhau, thì 2 gian hàng trống ở 2 đầu khối đó sẽ kề bên gian hàng đã thuê. Tuy nhiên, Yugi chỉ chọn 1 gian hàng. Vì sao tối thiểu luôn là 1? Xét trường hợp xấu nhất: Nếu ~k~ gian hàng được sắp xếp thành các khối riêng lẻ hoặc 1 khối dài, số lượng vị trí trống kề bên có thể là 1 (ví dụ: nếu ~k = n-1~, chỉ còn 1 vị trí trống và nó chắc chắn kề bên vị trí đã thuê). Vậy tối thiểu luôn là 1.
  • Tối đa: Yugi muốn tối đa hóa số lượng vị trí trống có ít nhất 1 hàng xóm đã thuê. Để tối đa hóa, ta cần tránh các vị trí trống 'đơn độc' ở 2 đầu dãy (nếu chúng không kề bên ai) và các vị trí trống ở giữa các đoạn trống dài. Ta cần tạo ra nhiều 'điểm biên' nhất.

Đề bài yêu cầu in ra số lượng tối thiểu và tối đa.

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

Cách Phân tích trực tiếp (Logic)

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;

    // Trường hợp cơ bản: không có gian hàng trống hoặc không có gian hàng thuê
    if (k == 0 || k == n) {
        cout << "0 0";
        return 0;
    }

    // Tối thiểu: Luôn luôn có ít nhất 1 lựa chọn (1)
    // Tối đa:
    // Để tối đa hóa, ta cần tối đa hóa số lượng đoạn 'một mình một chỗ' (1 0 1)
    // và các đầu mút.
    // Nếu ta sắp xếp các gian hàng thuê thành các nhóm 1 cái, xen kẽ với 2 chỗ trống (1 0 0 1 0 0 ...)
    // Mỗi gian hàng thuê tạo ra 2 vị trí trống kề bên (trừ đầu mút).
    // Tổng số vị trí trống kề bên tối đa là 2 * k.
    // Tuy nhiên, ta không thể vượt quá tổng số gian hàng trống là n - k.
    // Vậy tối đa là min(n - k, 2 * k).

    // Lưu ý: Solution 3 có check `if(k >= n/2) cout << n-k;`
    // Thực chất khi k >= n/2, n-k <= k. Khi đó min(n-k, 2*k) = n-k. 
    // Tất cả các vị trí trống đều kề bên vị trí thuê.

    cout << "1 " << min(n - k, 2 * k);

    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 việc nhận diện quy luật của bài toán.

1. Trường hợp đặc biệt: Nếu k = 0 hoặc k = n, kết quả là 0 0 vì không có vị trí trống hoặc không có hàng xóm.

2. Tối thiểu: Luôn là 1. Với k > 0 và k < n, luôn tồn tại ít nhất một vị trí trống kề bên vị trí đã thuê. Ví dụ, nếu các vị trí thuê tập trung ở một bên, ví dụ {1..k}, thì vị trí k+1 trống và kề bên k đã thuê.

3. Tối đa:

   • Tổng số vị trí trống là n - k.
   • Mỗi vị trí thuê có thể tạo ra tối đa 2 vị trí trống kề bên (trái và phải).
   • Nếu ta sắp xếp xen kẽ 1 đã thuê - 1 trống - 1 đã thuê, hoặc 1 đã thuê - 2 trống - 1 đã thuê, ta tối đa hóa số lượng vị trí trống được 'bao quanh'.
   • Tổng số vị trí trống kề bên tối đa có thể đạt được là 2 * k.
   • Tuy nhiên, ta không thể có nhiều vị trí trống hơn n - k.
   • Do đó, số lượng tối đa là min(n - k, 2 * k).

Cách Mô phỏng quy luật (Tối ưu hóa logic)

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;

    if (k == 0 || k == n) {
        cout << "0 0";
        return 0;
    }

    // Logic tương tự Approach 1 nhưng trình bày theo cách của Solution 3
    // Kiểm tra xem có đủ chỗ để sắp xếp xen kẽ không
    // Nếu k nhỏ, ta có thể tạo ra 2*k vị trí kề bên.
    // Nếu k lớn (k >= n/2), khi đó n-k <= k, nên min(n-k, 2*k) = n-k.

    int min_val = 1;
    int max_val;

    if (k >= n / 2) {
        max_val = n - k;
    } else {
        max_val = min(n - k, 2 * k); // Trong trường hợp k < n/2, 2*k < n-k (thường đúng khi n đủ lớn), nhưng giữ an toàn là min.
        // Thực tế khi k < n/2, 2*k < n-k.
        // Ví dụ n=10, k=3. 2*k=6, n-k=7. Max là 6.
    }

    // Tuy nhiên, giải pháp của Solution 2 là phổ biến nhất và ngắn gọn nhất:
    // cout << 1 << " " << min(n - k, 2 * k);

    cout << min_val << " " << max_val;

    return 0;
}

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

Phương pháp này là một biến thể của phương pháp 1, chia nhỏ vấn đề ra để dễ hiểu hơn.

• Kiểm tra điều kiện đầu vào k=0, k=n.
• So sánh k với n/2.
  • Nếu k >= n/2: Khoảng cách giữa các vị trí trống rất nhỏ, hoặc các vị trí trống bị cô lập ở 2 đầu. Thực tế, tất cả n-k vị trí trống đều kề bên vị trí thuê.
  • Nếu k < n/2: Ta có đủ không gian để sắp xếp các vị trí thuê tạo ra nhiều vị trí kề bên nhất (tối đa 2*k).
• Cuối cùng in ra 1 và giá trị tính được.

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

Bài học kinh nghiệm

• Với k > 0 và k < n, số lượng tối thiểu luôn là 1.
• Số lượng tối đa là min(n - k, 2 * k). Giới hạn trên là do số lượng vị trí trống thực tế (n-k) và giới hạn do mỗi vị trí thuê chỉ có thể kề tối đa 2 vị trí trống (2*k).

Lỗi thường gặp

• Xử lý sai trường hợp k = 0 hoặc k = n (cần in 0 0).
• Quên dùng long long cho biến n và k do n có thể lên tới 10^9 (trong các ngôn ngữ như C++/C#).