Hiểu bài toán

Bài toán yêu cầu tìm giá trị lớn nhất của độ dài mỗi mẩu kẹo (gọi là x) sao cho khi chia đều n viên kẹo ban đầu (với độ dài a[i]) thành các mẩu kẹo có độ dài x, ta thu được ít nhất m mẩu kẹo. Mỗi viên kẹo ban đầu có thể bị chia thành nhiều mẩu kẹo có độ dài x (số lượng là a[i] / x, phần dư bị loại bỏ). Cần tìm giá trị x lớn nhất thỏa mãn điều kiện.

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

Cách Tìm kiếm tuyến tính (Linear Search)

// Pseudocode:
int ans = 0;
for (int x = 1; x <= max_value; x++) {
    long long count = 0;
    for (int i = 0; i < n; i++) count += a[i] / x;
    if (count >= m) ans = x;
    else break; // Hoặc continue nếu muốn kiểm tra tất cả
}
cout << ans;

• Time Complexity: O(n * max_value)
• Space Complexity: O(1)

Cách tiếp cận này thử từng giá trị x từ 1 lên maxvalue. Với mỗi x, nó tính tổng số mẩu kẹo có được. Nếu thỏa mãn điều kiện, ta cập nhật kết quả. Tuy nhiên, đây là cách làm chậm chạp và chỉ hiệu quả nếu maxvalue rất nhỏ. Độ phức tạp phụ thuộc vào giá trị lớn nhất của kẹo, dẫn đến Time Limit Exceeded (TLE) cho các dữ liệu lớn.

Cách Tìm kiếm nhị phân (Binary Search)

#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
bool check(long x, long m) {
    int tong = 0;
    for(int i = 0; i < n; i++) tong += a[i] / x;
    return tong >= m;
}
int main() {
    int m;
    cin >> n >> m;
    a.resize(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    int l = 1, r = *max_element(a.begin(), a.end());
    long long kq = 0;
    while(l <= r) {
        long long sokeo = (l + r) / 2;
        if(check(sokeo, m)) {
            kq = sokeo;
            l = sokeo + 1;
        } else {
            r = sokeo - 1;
        }
    }
    cout << kq;
}

• Time Complexity: O(n log(max_value))
• Space Complexity: O(n)

Đây là phương pháp tối ưu nhất. Ta sử dụng đặc tính đơn điệu của bài toán: nếu ta có thể chia được kẹo với độ dài x để được >= m mẩu, thì ta chắc chắn cũng chia được với độ dài y (với y < x). Do đó, ta tìm kiếm giá trị x lớn nhất thỏa mãn điều kiện trong khoảng [1, max_value].

1. Thiết lập khoảng tìm kiếm l = 1, r = max(a[i]).
2. Lấy mid là giá trị ở giữa.
3. Hàm check(mid) tính tổng số mẩu kẹo nếu chia độ dài mid.
4. Nếu check(mid) đúng (tức là đủ số lượng mẩu), ta thử tìm giá trị lớn hơn bằng cách cập nhật l = mid + 1 và ghi nhận mid là kết quả tạm thời.
5. Nếu sai (không đủ mẩu), ta phải giảm giá trị xuống bằng cách r = mid - 1.
6. Vòng lặp kết thúc khi l > r. Kết quả là giá trị lớn nhất tìm được.

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

Bài học kinh nghiệm

• Bài toán có tính đơn điệu: Nếu độ dài x thỏa mãn điều kiện (tổng số mẩu >= m), thì mọi độ dài y < x cũng sẽ thỏa mãn. Ngược lại, nếu x không thỏa mãn, mọi y > x cũng không thỏa mãn.
• Sử dụng tìm kiếm nhị phân (Binary Search) để tìm giá trị tối ưu trong khoảng giá trị có thể của x (từ 1 đến max(a[i])) giúp giảm đáng kể thời gian thực hiện so với tìm kiếm tuần tự.

Lỗi thường gặp

• Sử dụng biến kiểu int để lưu tổng số mẩu kẹo hoặc giá trị kẹo có thể gây tràn số (Integer Overflow) nếu a[i] và m lớn. Nên dùng long long cho các biến tính toán tổng.
• Lựa chọn sai khoảng tìm kiếm ban đầu. Khoảng tìm kiếm phải bao phủ tất cả giá trị x có thể, cụ thể là từ 1 đến giá trị lớn nhất của kẹo.