Khóa học CTDL và GT

Bài 16.4. Ứng dụng Binary Search trong tối ưu hóa

Chào mừng các bạn đã quay trở lại với hành trình khám phá Cấu trúc dữ liệu và Giải thuật! Ở những bài trước, chúng ta đã làm quen với Binary Search (Tìm kiếm Nhị phân) như một kỹ thuật hiệu quả để tìm kiếm một phần tử trong một mảng hoặc danh sách đã được sắp xếp. Tuy nhiên, sức mạnh thực sự của Binary Search còn vượt xa hơn thế. Hôm nay, chúng ta sẽ đi sâu vào một trong những ứng dụng quan trọng và thú vị nhất của nó: ứng dụng Binary Search để giải quyết các bài toán tối ưu hóa.

Kỹ thuật này thường được gọi là "Binary Search on Answer" (Tìm kiếm Nhị phân trên kết quả). Thay vì tìm kiếm một phần tử trong một tập dữ liệu, chúng ta sẽ tìm kiếm một giá trị tối ưu nằm trong một phạm vi các giá trị có thể có của đáp án.

Khái niệm cốt lõi: Tính chất đơn điệu (Monotonic Property)

Tại sao Binary Search lại có thể áp dụng cho bài toán tối ưu hóa? Lý do nằm ở tính chất đơn điệu (monotonic property) của vấn đề. Đối với các bài toán mà Binary Search on Answer có thể giải quyết, thường tồn tại một giá trị X sao cho:

1. Nếu một giá trị V lớn hơn hoặc bằng X thỏa mãn một điều kiện nào đó, thì tất cả các giá trị V' lớn hơn V cũng sẽ thỏa mãn điều kiện đó. (Tìm kiếm giá trị nhỏ nhất thỏa mãn điều kiện).
2. Hoặc ngược lại, nếu một giá trị V nhỏ hơn hoặc bằng X thỏa mãn một điều kiện nào đó, thì tất cả các giá trị V' nhỏ hơn V cũng sẽ thỏa mãn điều kiện đó. (Tìm kiếm giá trị lớn nhất thỏa mãn điều kiện).

Nói cách khác, tập hợp các giá trị thỏa mãn điều kiện có dạng một "đoạn" hoặc "nửa khoảng" trên trục số. Điều này tạo ra một ranh giới giữa các giá trị thỏa mãn và không thỏa mãn, và chính ranh giới này là thứ mà Binary Search có thể tìm thấy một cách hiệu quả.

Ví dụ đơn giản: Hãy tưởng tượng bài toán "Tìm thời gian tối thiểu để hoàn thành tất cả công việc". Nếu bạn có thể hoàn thành tất cả công việc trong T giờ, chắc chắn bạn cũng có thể hoàn thành chúng trong T + 1, T + 2, v.v... giờ. Đây là tính chất đơn điệu: khả năng hoàn thành công việc trong thời gian T kéo theo khả năng hoàn thành trong mọi thời gian T' > T. Chúng ta đang tìm kiếm thời gian T nhỏ nhất mà điều kiện "hoàn thành tất cả công việc" là đúng.

Hàm kiểm tra (check() function) - Trái tim của Binary Search on Answer

Để áp dụng Binary Search on Answer, chúng ta cần xây dựng một hàm gọi là check(X). Hàm này sẽ nhận một giá trị X (là một ứng viên cho đáp án) và trả về true nếu X thỏa mãn điều kiện của bài toán, và false nếu ngược lại.

• Hàm check(X) phải được thiết kế sao cho nó có tính chất đơn điệu như đã mô tả ở trên.
• Việc tính toán trong hàm check(X) phải đủ hiệu quả (thường là O(N), O(N log N) hoặc O(1), không quá chậm) vì nó sẽ được gọi nhiều lần bên trong vòng lặp Binary Search.

Sau khi có hàm check(X) và xác định được phạm vi tìm kiếm cho đáp án [L, R], chúng ta có thể áp dụng Binary Search để tìm ra giá trị tối ưu.

Cấu trúc thuật toán chung

1. Xác định phạm vi tìm kiếm [L, R]: Đây là phạm vi mà đáp án cuối cùng chắc chắn nằm trong đó. L là giá trị nhỏ nhất có thể, R là giá trị lớn nhất có thể của đáp án. Việc xác định phạm vi này là rất quan trọng.
2. Xây dựng hàm check(X): Hàm này kiểm tra xem giá trị X có thỏa mãn điều kiện của bài toán hay không.
3. Áp dụng Binary Search:
   • Khởi tạo L và R.
   • Khởi tạo biến ans để lưu trữ đáp án tốt nhất tìm được cho đến nay (ban đầu có thể là R hoặc L tùy bài toán và hướng tìm kiếm).
   • Trong khi L <= R (hoặc L < R, tùy cách cài đặt và kiểu dữ liệu):
     • Tính giá trị giữa: mid = L + (R - L) / 2. Sử dụng cách tính này để tránh tràn số khi L và R rất lớn.
     • Gọi check(mid):
       • Nếu check(mid) trả về true: mid là một giá trị có thể là đáp án hoặc thậm chí tốt hơn (tức là chúng ta có thể đạt được điều kiện với giá trị mid). Lưu lại mid là một ứng viên tốt (ans = mid) và tiếp tục tìm kiếm ở nửa phạm vi còn lại để tìm giá trị tốt hơn (nhỏ hơn nếu tìm min, lớn hơn nếu tìm max). Ví dụ, nếu tìm min: R = mid - 1. Nếu tìm max: L = mid + 1.
       • Nếu check(mid) trả về false: mid không thỏa mãn điều kiện, tức là mid quá lớn (nếu tìm min) hoặc quá nhỏ (nếu tìm max). Loại bỏ mid và nửa phạm vi chứa nó. Ví dụ, nếu tìm min: L = mid + 1. Nếu tìm max: R = mid - 1.
   • Sau vòng lặp, biến ans (hoặc đôi khi là giá trị cuối cùng của L hoặc R) sẽ chứa đáp án tối ưu.

Hãy cùng xem qua một vài ví dụ minh họa để hiểu rõ hơn.

Ví dụ 1: Bài toán "Aggressive Cows" (Những chú bò hung hăng)

Mô tả bài toán: Cho N chuồng trại nằm dọc theo một đường thẳng tại các vị trí x_1, x_2, ..., x_N. Bạn cần nhốt K con bò vào các chuồng sao cho khoảng cách nhỏ nhất giữa hai con bò bất kỳ là lớn nhất có thể. Tìm khoảng cách nhỏ nhất lớn nhất này.

• Input: N (số chuồng), K (số bò), và một vector chứa N vị trí chuồng trại (các vị trí này không nhất thiết phải theo thứ tự).
• Output: Khoảng cách nhỏ nhất lớn nhất giữa hai con bò.

Phân tích: Chúng ta cần tìm một khoảng cách D sao cho ta có thể nhốt K con bò vào các chuồng và khoảng cách giữa hai con bò bất kỳ luôn >= D, và D là giá trị lớn nhất có thể.

• Phạm vi tìm kiếm cho đáp án (khoảng cách D):

  • Giá trị nhỏ nhất có thể của D là 0.
  • Giá trị lớn nhất có thể của D là khoảng cách giữa chuồng xa nhất và chuồng gần nhất (sau khi đã sắp xếp các vị trí).
  • Vậy, phạm vi là [0, positions.back() - positions.front()] sau khi sắp xếp các vị trí.

• Hàm check(D): Kiểm tra xem có thể nhốt K con bò vào các chuồng sao cho khoảng cách nhỏ nhất giữa chúng là ít nhất D hay không.

  • Để kiểm tra điều này một cách tham lam (greedy): Đặt con bò đầu tiên vào chuồng đầu tiên. Sau đó, với mỗi con bò tiếp theo, tìm chuồng đầu tiên (từ trái sang phải) mà nó có thể được đặt vào sao cho khoảng cách đến con bò trước đó ít nhất là D. Đếm số con bò nhốt được.
  • Hàm check(D) trả về true nếu số bò nhốt được >= K, ngược lại trả về false.
  • Tính chất đơn điệu: Nếu bạn có thể nhốt K con bò với khoảng cách nhỏ nhất là D, bạn chắc chắn có thể nhốt K con bò với khoảng cách nhỏ nhất là D' với D' < D. Điều kiện "nhốt được K con bò với khoảng cách min >= D" là đơn điệu giảm theo D. Chúng ta đang tìm D lớn nhất mà điều kiện này đúng.

Cài đặt (C++):

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm kiểm tra: Với khoảng cách min `d`, có thể đặt được `k` con bò không?
bool can_place_cows(long long d, int k, const std::vector<int>& positions) {
    int count = 1; // Đặt con bò đầu tiên vào chuồng đầu tiên
    int last_pos = positions[0]; // Vị trí của con bò cuối cùng được đặt

    for (size_t i = 1; i < positions.size(); ++i) {
        // Nếu khoảng cách từ chuồng hiện tại đến con bò cuối cùng >= d
        if (positions[i] - last_pos >= d) {
            count++; // Đặt thêm một con bò
            last_pos = positions[i]; // Cập nhật vị trí con bò cuối cùng
            if (count == k) {
                return true; // Đã đặt đủ k con bò
            }
        }
    }
    // Nếu duyệt hết các chuồng mà chưa đặt đủ k con bò
    return false;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n; // Số chuồng
    int k; // Số bò
    std::cin >> n >> k;

    std::vector<int> positions(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> positions[i];
    }

    // Bước 1: Sắp xếp vị trí các chuồng
    std::sort(positions.begin(), positions.end());

    // Bước 2: Xác định phạm vi tìm kiếm cho khoảng cách D
    long long low = 0; // Khoảng cách nhỏ nhất có thể là 0
    long long high = positions.back() - positions.front(); // Khoảng cách lớn nhất có thể
    long long ans = 0; // Biến lưu trữ đáp án tốt nhất

    // Bước 3: Áp dụng Binary Search trên phạm vi [low, high]
    while (low <= high) {
        long long mid = low + (high - low) / 2; // Tính giá trị giữa

        // Kiểm tra xem có thể đặt k con bò với khoảng cách min là `mid` không
        if (can_place_cows(mid, k, positions)) {
            // Nếu có thể, `mid` là một đáp án khả thi.
            // Vì ta muốn tìm khoảng cách *lớn nhất*, nên lưu lại `mid`
            // và thử tìm kiếm ở nửa bên phải (khoảng cách lớn hơn).
            ans = mid;
            low = mid + 1;
        } else {
            // Nếu không thể, `mid` quá lớn.
            // Ta phải tìm kiếm ở nửa bên trái (khoảng cách nhỏ hơn).
            high = mid - 1;
        }
    }

    // `ans` chứa khoảng cách nhỏ nhất lớn nhất tìm được
    std::cout << ans << std::endl;

    return 0;
}

Giải thích code:

1. Chúng ta có hàm can_place_cows(long long d, int k, const std::vector<int>& positions) làm nhiệm vụ check(d). Nó tham lam đặt con bò đầu tiên ở positions[0]. Sau đó, nó duyệt qua các chuồng còn lại, tìm chuồng đầu tiên có vị trí cách vị trí con bò cuối cùng đã đặt một khoảng ít nhất là d. Nếu tìm thấy, nó đặt con bò tiếp theo vào đó và tăng biến đếm count. Quá trình dừng lại khi đã đặt đủ k con bò hoặc duyệt hết các chuồng. Hàm trả về true nếu count >= k, false nếu ngược lại.
2. Trong main, chúng ta đọc input, sắp xếp mảng positions.
3. Xác định phạm vi tìm kiếm [low, high]. low = 0 là khoảng cách nhỏ nhất không ý nghĩa (bò sát nhau). high là khoảng cách lớn nhất có thể giữa hai chuồng xa nhất.
4. Vòng lặp while (low <= high) thực hiện Binary Search.
5. mid là điểm giữa của phạm vi hiện tại.
6. Gọi can_place_cows(mid, k, positions).
   • Nếu kết quả là true: Điều này có nghĩa là khoảng cách mid là khả thi. Vì chúng ta muốn lớn nhất khoảng cách khả thi, mid là một ứng viên đáp án tốt hơn hoặc bằng các ứng viên trước. Ta lưu nó vào ans và thử tìm kiếm khoảng cách lớn hơn trong nửa trên của phạm vi: low = mid + 1.
   • Nếu kết quả là false: Khoảng cách mid là không khả thi (quá lớn). Đáp án phải nhỏ hơn mid. Ta loại bỏ mid và nửa trên, tiếp tục tìm kiếm trong nửa dưới: high = mid - 1.
7. Khi vòng lặp kết thúc (low > high), ans sẽ giữ giá trị khoảng cách lớn nhất mà vẫn cho phép đặt được k con bò.

Ví dụ 2: Bài toán "Cắt gỗ" (Wood Cutting)

Mô tả bài toán: Cho N khúc gỗ với độ dài lần lượt là L_1, L_2, ..., L_N. Bạn cần cắt ra K khúc gỗ mới có độ dài bằng nhau. Hãy tìm độ dài lớn nhất có thể của K khúc gỗ mới này. Bạn chỉ có thể cắt từ các khúc gỗ ban đầu, không được ghép chúng lại.

• Input: N (số khúc gỗ ban đầu), K (số khúc gỗ cần cắt), và một vector chứa N độ dài khúc gỗ ban đầu.
• Output: Độ dài lớn nhất có thể của K khúc gỗ mới.

Phân tích: Chúng ta cần tìm một độ dài Len sao cho từ các khúc gỗ ban đầu có thể cắt được ít nhất K khúc gỗ con có độ dài Len. Chúng ta muốn tìm Len là giá trị lớn nhất có thể.

• Phạm vi tìm kiếm cho đáp án (độ dài Len):

  • Giá trị nhỏ nhất có thể của Len là 0.
  • Giá trị lớn nhất có thể của Len là độ dài của khúc gỗ dài nhất trong input (vì bạn không thể cắt một khúc gỗ dài hơn khúc gỗ dài nhất ban đầu).
  • Vậy, phạm vi là [0, max(lengths)].

• Hàm check(Len): Kiểm tra xem có thể cắt được ít nhất K khúc gỗ con có độ dài Len từ các khúc gỗ ban đầu hay không.

  • Với mỗi khúc gỗ ban đầu có độ dài L_i, ta có thể cắt được floor(L_i / Len) khúc gỗ con có độ dài Len. (Lưu ý: nếu Len là 0, số khúc gỗ con là vô hạn, trường hợp này thường không xảy ra trong phạm vi tìm kiếm hữu ích hoặc cần xử lý riêng).
  • Tổng số khúc gỗ con có độ dài Len cắt được là sum(floor(L_i / Len)) trên tất cả các khúc gỗ ban đầu.
  • Hàm check(Len) trả về true nếu tổng số khúc gỗ con >= K, ngược lại trả về false.
  • Tính chất đơn điệu: Nếu bạn có thể cắt được K khúc gỗ con với độ dài Len, bạn chắc chắn có thể cắt được K khúc gỗ con với độ dài Len' với Len' < Len. Điều kiện "cắt được ít nhất K khúc gỗ con có độ dài Len" là đơn điệu giảm theo Len. Chúng ta đang tìm Len lớn nhất mà điều kiện này đúng.

Cài đặt (C++):

#include <iostream>
#include <vector>
#include <numeric> // For std::accumulate (optional, not used in final check)
#include <algorithm> // For std::max

// Hàm kiểm tra: Với độ dài `len`, có thể cắt được ít nhất `k` khúc gỗ không?
bool can_cut(long long len, int k, const std::vector<int>& lengths) {
    if (len == 0) { // Xử lý trường hợp len = 0, có thể cắt vô số khúc gỗ
        return true; // Nếu k > 0, ta có thể cắt được. Nếu k = 0, cũng đúng.
                     // Tuy nhiên, trong binary search, len=0 thường là low bound và check(0) luôn true.
                     // Ta quan tâm đến len > 0.
    }
    long long count = 0; // Tổng số khúc gỗ con cắt được
    for (int l : lengths) {
        count += l / len; // Số khúc gỗ con độ dài 'len' từ khúc gỗ dài 'l'
        if (count >= k) {
             return true; // Đã đủ hoặc thừa k khúc gỗ, không cần kiểm tra thêm
        }
    }
    return count >= k; // Kiểm tra lại sau khi duyệt hết
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n; // Số khúc gỗ ban đầu
    int k; // Số khúc gỗ cần cắt
    std::cin >> n >> k;

    std::vector<int> lengths(n);
    int max_len = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> lengths[i];
        if (lengths[i] > max_len) {
            max_len = lengths[i];
        }
    }

    // Bước 1: Xác định phạm vi tìm kiếm cho độ dài Len
    // Có thể cắt khúc gỗ có độ dài từ 0 đến độ dài khúc gỗ dài nhất ban đầu
    long long low = 0;
    long long high = max_len; // Độ dài lớn nhất có thể của khúc gỗ con

    // Biến lưu trữ đáp án tốt nhất
    long long ans = 0; // Độ dài lớn nhất tìm được

    // Bước 2: Áp dụng Binary Search trên phạm vi [low, high]
    while (low <= high) {
        long long mid = low + (high - low) / 2; // Tính giá trị giữa

        // Kiểm tra xem có thể cắt ít nhất k khúc gỗ với độ dài `mid` không
        if (can_cut(mid, k, lengths)) {
            // Nếu có thể, `mid` là một đáp án khả thi.
            // Vì ta muốn tìm độ dài *lớn nhất*, nên lưu lại `mid`
            // và thử tìm kiếm ở nửa bên phải (độ dài lớn hơn).
            ans = mid;
            low = mid + 1;
        } else {
            // Nếu không thể, độ dài `mid` quá lớn.
            // Ta phải tìm kiếm ở nửa bên trái (độ dài nhỏ hơn).
            high = mid - 1;
        }
    }

    // `ans` chứa độ dài lớn nhất có thể của k khúc gỗ
    std::cout << ans << std::endl;

    return 0;
}

Giải thích code:

1. Hàm can_cut(long long len, int k, const std::vector<int>& lengths) kiểm tra xem với độ dài len có thể cắt được ít nhất k khúc gỗ không. Nó duyệt qua từng khúc gỗ ban đầu l và tính số khúc gỗ con cắt được là l / len (sử dụng phép chia số nguyên để tự động làm tròn xuống). Tổng số khúc gỗ con được cộng dồn vào count. Nếu count đạt k hoặc hơn, ta có thể dừng lại và trả về true.
2. Trong main, chúng ta đọc input và tìm độ dài khúc gỗ lớn nhất để xác định high cho phạm vi tìm kiếm.
3. Phạm vi tìm kiếm là [low, high], với low = 0 và high = max_len.
4. Vòng lặp Binary Search hoạt động tương tự ví dụ trước.
5. Gọi can_cut(mid, k, lengths).
   • Nếu kết quả là true: Độ dài mid là khả thi. Vì muốn lớn nhất độ dài khả thi, mid là một ứng viên tốt. Lưu ans = mid và tìm kiếm độ dài lớn hơn: low = mid + 1.
   • Nếu kết quả là false: Độ dài mid là không khả thi. Quá lớn. Tìm kiếm độ dài nhỏ hơn: high = mid - 1.
6. Kết quả cuối cùng lưu trong ans.

Ví dụ 3: Bài toán "Thời gian hoàn thành nhiệm vụ song song"

Mô tả bài toán: Bạn có N nhiệm vụ và M công nhân. Mỗi công nhân i mất một khoảng thời gian cố định time[i] để hoàn thành một nhiệm vụ. Các công nhân có thể làm việc song song. Một công nhân chỉ làm một nhiệm vụ tại một thời điểm. Tìm thời gian ít nhất để hoàn thành tất cả N nhiệm vụ.

• Input: N (tổng số nhiệm vụ), M (số công nhân), và một vector chứa M thời gian hoàn thành một nhiệm vụ cho mỗi công nhân.
• Output: Thời gian tối thiểu để hoàn thành N nhiệm vụ.

Phân tích: Chúng ta cần tìm một khoảng thời gian T sao cho trong khoảng thời gian T, M công nhân có thể hoàn thành ít nhất N nhiệm vụ. Chúng ta muốn tìm T là giá trị nhỏ nhất có thể.

• Phạm vi tìm kiếm cho đáp án (thời gian T):

  • Giá trị nhỏ nhất có thể của T là 0.
  • Giá trị lớn nhất có thể của T có thể là thời gian mà công nhân chậm nhất hoàn thành tất cả N nhiệm vụ một mình (nếu chỉ có 1 công nhân): max_worker_time * N. Hoặc một cận trên an toàn đủ lớn (ví dụ: 10^14 hoặc 10^15 nếu N và time[i] lên đến 10^9). Cần sử dụng kiểu dữ liệu long long cho T và các biến liên quan.
  • Phạm vi là [0, max_worker_time * N] hoặc một cận trên đủ lớn như [0, 1e14].

• Hàm check(T): Kiểm tra xem trong thời gian T, M công nhân có thể hoàn thành ít nhất N nhiệm vụ hay không.

  • Trong thời gian T, công nhân i (mất time[i] để làm 1 nhiệm vụ) có thể hoàn thành floor(T / time[i]) nhiệm vụ.
  • Tổng số nhiệm vụ hoàn thành trong thời gian T là sum(floor(T / time[i])) trên tất cả M công nhân.
  • Hàm check(T) trả về true nếu tổng số nhiệm vụ hoàn thành >= N, ngược lại trả về false.
  • Tính chất đơn điệu: Nếu trong thời gian T có thể hoàn thành N nhiệm vụ, chắc chắn trong thời gian T' với T' > T cũng có thể hoàn thành N nhiệm vụ. Điều kiện "hoàn thành ít nhất N nhiệm vụ trong thời gian T" là đơn điệu tăng theo T. Chúng ta đang tìm T nhỏ nhất mà điều kiện này đúng.

Cài đặt (C++):

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// Hàm kiểm tra: Trong thời gian `t`, có thể hoàn thành ít nhất `n` nhiệm vụ không?
bool can_complete_tasks(long long t, long long n, const std::vector<int>& times) {
    // Nếu thời gian t là âm (không xảy ra trong binary search của ta), hoặc 0
    // và n > 0, thì không thể hoàn thành.
    if (t < 0) return false;
    if (t == 0 && n > 0) return false;
    if (n == 0) return true; // 0 nhiệm vụ luôn hoàn thành trong mọi thời gian >= 0

    long long completed_tasks = 0;
    for (int worker_time : times) {
        // Số nhiệm vụ công nhân này có thể làm trong thời gian `t`
        // Chú ý: Tránh tràn số nếu t và worker_time rất lớn, nhưng ở đây times[i] nhỏ
        // và t là mid trong binary search, nên t / worker_time vẫn trong giới hạn long long.
        if (worker_time > 0) { // Đảm bảo worker_time > 0 để tránh chia cho 0
             completed_tasks += t / worker_time;
        }
        // Nếu số nhiệm vụ hoàn thành đã đủ, không cần tính thêm
        if (completed_tasks >= n) {
            return true;
        }
    }
    return completed_tasks >= n; // Kiểm tra lại tổng sau khi duyệt hết
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int m; // Số công nhân
    long long n; // Số nhiệm vụ
    std::cin >> n >> m;

    std::vector<int> times(m);
    int min_worker_time = -1;
    int max_worker_time = 0;
    for (int i = 0; i < m; ++i) {
        std::cin >> times[i];
        if (min_worker_time == -1 || times[i] < min_worker_time) {
            min_worker_time = times[i];
        }
        if (times[i] > max_worker_time) {
            max_worker_time = times[i];
        }
    }

    // Bước 1: Xác định phạm vi tìm kiếm cho thời gian T
    // Thời gian nhỏ nhất có thể là 0.
    // Thời gian lớn nhất có thể: công nhân chậm nhất làm tất cả N nhiệm vụ.
    // Hoặc một cận trên an toàn lớn hơn. Ví dụ 10^14 hoặc 10^15.
    // Cần đảm bảo high đủ lớn. Nếu n = 10^9 và max_worker_time = 10^9, tích là 10^18.
    // Tuy nhiên, trong thực tế, max_worker_time thường nhỏ hơn.
    // Một cận trên an toàn là max_worker_time * n, nhưng cần kiểm tra tràn số.
    // Nếu n <= 10^9 và max_worker_time <= 10^9, tích có thể lên tới 10^18, cần long long.
    // Một cách khác là dùng một cận trên cố định lớn, ví dụ 1e14 hoặc 1e15.
    // Với n = 10^9 và times[i] = 1, thời gian là 1.
    // Với n = 10^9 và times[i] = 10^5, thời gian cần khoảng 10^9 * 10^5 / số công nhân.
    // Nếu chỉ 1 công nhân, 10^14.
    // Cận trên max_worker_time * n có thể tràn long long nếu n và max_worker_time đều lớn.
    // Một cận trên an toàn hơn: n * min_worker_time (nếu chỉ có công nhân nhanh nhất) là cận dưới,
    // n * max_worker_time là cận trên lỏng.
    // Nếu N = 10^9, min_time = 1, high = 10^9 (nếu có nhiều công nhân nhanh).
    // Nếu N = 10^9, max_time = 10^9, m = 1, high = 10^18.
    // Ok, dùng cận trên đủ lớn như 1e14 hoặc tính toán cẩn thận max_worker_time * n.
    // Giả sử times[i] không quá lớn (ví dụ <= 10^5), N <= 10^9. High có thể tới 10^5 * 10^9 = 10^14.
    // Sử dụng 10^14 làm high là an toàn trong nhiều trường hợp competitive programming.
    // Tuy nhiên, công thức tính chính xác high là:
    // Nếu chỉ có 1 công nhân: high = (long long)max_worker_time * n;
    // Nếu có nhiều công nhân nhanh: high = (long long)min_worker_time * n;
    // Nhưng cần tìm min time, nên high phải là trường hợp tệ nhất (công nhân chậm nhất làm nhiều nhất).
    // Một cách ước lượng high an toàn: thời gian để 1 công nhân chậm nhất làm hết: (long long)max_worker_time * n
    // Hoặc thời gian để 1 công nhân nhanh nhất làm hết: (long long)min_worker_time * n.
    // Cận trên thực tế không vượt quá n * max_worker_time (nếu chỉ có 1 công nhân)
    // Nhưng vì có M công nhân, high sẽ nhỏ hơn nhiều.
    // Một cách ước lượng high: Giả sử tất cả công nhân đều nhanh nhất: N nhiệm vụ / (M công nhân / nhiệm vụ/thời gian)
    // Thời gian = N * time_per_task / M.
    // Cận trên an toàn: (long long)max_worker_time * n (quá lớn)
    // Cận trên hợp lý: (long long)max_worker_time * n / m (ước lượng)
    // Cận trên an toàn và thường đủ: 10^14 hoặc 10^15.
    // Ta dùng một giá trị lớn đủ an toàn cho hầu hết các bài toán.
    long long low = 0;
    long long high = 2e14; // Một cận trên an toàn (vd: 2 * 10^14) - cần kiểm tra giới hạn bài toán cụ thể!
                          // Nếu max_worker_time <= 10^9, N <= 10^9, thì max_worker_time * N có thể ~10^18, cần high lớn hơn.
                          // Nếu N, M <= 10^5, times[i] <= 10^9. Max time ~ 10^9. Total tasks ~ N/M * time ~ 10^5/1 * 10^9 = 10^14.
                          // ok, 2e14 có vẻ ổn cho nhiều bài.
    long long ans = high; // Ban đầu coi thời gian lớn nhất có thể là đáp án tệ nhất

    // Bước 2: Áp dụng Binary Search trên phạm vi [low, high]
    while (low <= high) {
        long long mid = low + (high - low) / 2; // Tính giá trị giữa

        // Kiểm tra xem trong thời gian `mid`, có thể hoàn thành ít nhất `n` nhiệm vụ không
        if (can_complete_tasks(mid, n, times)) {
            // Nếu có thể, `mid` là một khoảng thời gian đủ.
            // Vì ta muốn tìm thời gian *ít nhất*, nên lưu lại `mid`
            // và thử tìm kiếm ở nửa bên trái (thời gian nhỏ hơn).
            ans = mid;
            high = mid - 1;
        } else {
            // Nếu không thể, thời gian `mid` là không đủ.
            // Ta phải tìm kiếm ở nửa bên phải (thời gian lớn hơn).
            low = mid + 1;
        }
    }

    // `ans` chứa thời gian ít nhất để hoàn thành n nhiệm vụ
    std::cout << ans << std::endl;

    return 0;
}

Giải thích code:

1. Hàm can_complete_tasks(long long t, long long n, const std::vector<int>& times) là hàm check(t). Nó tính tổng số nhiệm vụ mà tất cả công nhân có thể hoàn thành trong thời gian t. Đối với mỗi công nhân mất worker_time để làm một nhiệm vụ, trong thời gian t, họ làm được t / worker_time nhiệm vụ (sử dụng phép chia số nguyên). Tổng số nhiệm vụ được cộng dồn. Nếu tổng completed_tasks đạt hoặc vượt quá n, hàm trả về true.
2. Trong main, đọc input n, m và vector times.
3. Xác định phạm vi tìm kiếm [low, high]. low = 0. high được chọn là một giá trị đủ lớn để đảm bảo đáp án nằm trong phạm vi này. Việc chọn cận trên an toàn cần cân nhắc giới hạn của bài toán cụ thể.
4. Binary Search được thực hiện trên phạm vi thời gian [low, high].
5. Gọi can_complete_tasks(mid, n, times).
   • Nếu kết quả là true: Thời gian mid là đủ để hoàn thành n nhiệm vụ. Vì muốn ít nhất thời gian, mid là một ứng viên tốt. Lưu ans = mid và tìm kiếm thời gian nhỏ hơn trong nửa dưới: high = mid - 1.
   • Nếu kết quả là false: Thời gian mid là không đủ. Đáp án phải lớn hơn mid. Tìm kiếm thời gian lớn hơn trong nửa trên: low = mid + 1.
6. Khi vòng lặp kết thúc, ans chứa thời gian tối thiểu.

Bài tập ví dụ:

Chẵn lẻ bằng nhau

Trong một dự án nghiên cứu về trí tuệ nhân tạo, FullHouse Dev đang phát triển một thuật toán để phân tích dữ liệu số. Họ gặp phải một bài toán thú vị liên quan đến việc cân bằng số lượng số chẵn trong một mảng. Với sự tò mò và nhiệt huyết, nhóm bắt đầu giải quyết thách thức này.

Bài toán

FullHouse Dev được cung cấp một mảng \(A\) chứa \(N\) số nguyên. Mục tiêu là đạt được chính xác \(K\) số chẵn trong mảng. Họ có thể thực hiện thao tác sau đây bất kỳ số lần nào (có thể là 0 lần):

Chọn hai chỉ số khác nhau \(i\) và \(j\) sao cho \(A_i + A_j\) là một số chẵn, sau đó đặt \(A_i = A_j = (A_i + A_j)/2\).

Nhiệm vụ của nhóm là xác định xem có thể đạt được mục tiêu hay không.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Với mỗi test case:
  • Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), trong đó \(N\) là kích thước của mảng \(A\).
  • Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, ..., A_N\) - các phần tử của mảng \(A\).

OUTPUT FORMAT:

• Với mỗi test case, in ra "YES" (không có dấu ngoặc kép) nếu có thể đạt được mục tiêu và "NO" (không có dấu ngoặc kép) nếu không thể.

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(2 \leq N \leq 10^5\)
• \(0 \leq K \leq N\)
• \(1 \leq A_i \leq 10^9\)
• Tổng của \(N\) trong tất cả các test case không vượt quá \(10^6\).

Ví dụ

INPUT

2
4 2
1 2 3 5
4 2
8 5 1 3

OUTPUT

NO
YES

Giải thích

• Ở test case đầu tiên, không thể đạt được chính xác 2 số chẵn trong mảng đã cho.
• Ở test case thứ hai, FullHouse Dev có thể áp dụng thao tác trên các chỉ số 1 và 4, làm cho \(A_1 = A_4 = (8 + 3)/2 = 5.5\), kết quả là mảng \([5.5, 5, 1, 5.5]\) chứa đúng 2 số chẵn.

FullHouse Dev nhận ra rằng bài toán này không chỉ thú vị về mặt toán học mà còn có thể áp dụng trong việc cân bằng dữ liệu cho các mô hình AI. Họ tiếp tục nghiên cứu để tìm ra các ứng dụng thực tế cho thuật toán này trong lĩnh vực trí tuệ nhân tạo. Okay, đây là hướng dẫn giải bài toán "Chẵn lẻ bằng nhau" dựa trên phân tích thao tác và các ràng buộc:

1. Phân tích thao tác: Thao tác cho phép bạn chọn hai chỉ số i và j khác nhau sao cho A[i] + A[j] là số chẵn, sau đó đặt A[i] = A[j] = (A[i] + A[j]) / 2.

   • Điều kiện A[i] + A[j] là số chẵn chỉ xảy ra khi A[i] và A[j] có cùng tính chẵn lẻ (cùng chẵn hoặc cùng lẻ).
   • Nếu A[i] và A[j] cùng chẵn: (Chẵn + Chẵn) / 2 = Chẵn / 2. Kết quả có thể là số chẵn hoặc số lẻ (ví dụ: (2+6)/2=4 (chẵn), (2+4)/2=3 (lẻ)).
   • Nếu A[i] và A[j] cùng lẻ: (Lẻ + Lẻ) / 2 = Chẵn / 2. Kết quả có thể là số chẵn hoặc số lẻ (ví dụ: (1+3)/2=2 (chẵn), (1+5)/2=3 (lẻ)).
   • Quan trọng: Thao tác luôn thay thế hai số cùng tính chẵn lẻ bằng hai số có cùng tính chẵn lẻ mới. Ví dụ, nếu kết quả (A[i]+A[j])/2 là lẻ, cả A[i] và A[j] đều trở thành lẻ. Nếu kết quả là chẵn, cả hai đều trở thành chẵn.

2. Phân tích sự thay đổi về số lượng số lẻ/chẵn:

   • Ghép 2 số chẵn: Số lượng số chẵn có thể không đổi (E,E -> E,E) hoặc giảm đi 2 (E,E -> O,O).
   • Ghép 2 số lẻ: Số lượng số chẵn có thể tăng lên 2 (O,O -> E,E) hoặc không đổi (O,O -> O,O).
   • Trong mọi trường hợp, số lượng số chẵn (và số lượng số lẻ) trong mảng chỉ thay đổi đi 0 hoặc 2 đơn vị.
   • Điều này có nghĩa là tính chẵn lẻ của tổng số số chẵn (hoặc tổng số số lẻ) trong mảng là một bất biến (invariant). Tổng số số chẵn ban đầu và tổng số số chẵn cuối cùng phải có cùng tính chẵn lẻ.

3. Điều kiện cần từ bất biến:

   • Đếm số lượng số lẻ ban đầu trong mảng (initial_odd_count).
   • Số lượng số chẵn ban đầu là initial_even_count = N - initial_odd_count.
   • Mục tiêu là đạt được K số chẵn.
   • Điều kiện cần là: K % 2 == initial_even_count % 2.
   • Điều này tương đương với K % 2 == (N - initial_odd_count) % 2.

4. Các trường hợp đặc biệt (Khi không đủ cặp để thao tác):

   • Thao tác yêu cầu chọn hai chỉ số khác nhau có cùng tính chẵn lẻ. Nếu chỉ có một số lẻ duy nhất trong mảng, số lẻ đó không thể được ghép cặp với bất kỳ số nào khác (vì các số còn lại đều chẵn và phải ghép với số cùng tính chẵn lẻ). Do đó, số lẻ duy nhất đó sẽ không bao giờ thay đổi tính chẵn lẻ.
   • Tương tự, nếu chỉ có một số chẵn duy nhất trong mảng, số chẵn đó sẽ không bao giờ thay đổi tính chẵn lẻ.
   • Nếu initial_odd_count == 1: Số lẻ duy nhất bị "kẹt" là lẻ. Số lượng số lẻ cuối cùng (N - K) không thể bằng 0. Tức là N - K >= 1.
   • Nếu initial_even_count == 1: Số chẵn duy nhất bị "kẹt" là chẵn. Số lượng số chẵn cuối cùng (K) không thể bằng 0. Tức là K >= 1.

5. Kết hợp các điều kiện:

   • Đếm số lượng số lẻ ban đầu (odd_count). Số lượng số chẵn ban đầu là even_count = N - odd_count.
   • Mục tiêu là K số chẵn. Số lượng số lẻ mục tiêu là target_odd = N - K.
   • Điều kiện 1 (Từ bất biến): K % 2 == even_count % 2.
   • Điều kiện 2 (Từ số lẻ bị kẹt): Nếu odd_count == 1, thì target_odd >= 1.

   • Điều kiện 3 (Từ số chẵn bị kẹt): Nếu even_count == 1, thì K >= 1.

   • Kết quả là "YES" nếu tất cả các điều kiện sau được thỏa mãn, ngược lại là "NO":

     1. K % 2 == even_count % 2
     2. Nếu odd_count == 1, thì target_odd >= 1. (Điều này có thể viết lại là: Nếu odd_count == 1 và target_odd == 0, thì không thể).
     3. Nếu even_count == 1, thì K >= 1. (Điều này có thể viết lại là: Nếu even_count == 1 và K == 0, thì không thể).

   • Lưu ý: Nếu odd_count != 1 và even_count != 1, thì có ít nhất 2 số lẻ (nếu odd_count >= 2) và ít nhất 2 số chẵn (nếu even_count >= 2). Trong trường hợp này, luôn có thể thực hiện các thao tác O+O hoặc E+E để thay đổi số lượng chẵn/lẻ theo cặp +/- 2, và bất biến về tính chẵn lẻ của số lượng chẵn/lẻ đảm bảo bạn có thể đạt được mọi số lượng có cùng tính chẵn lẻ mục tiêu trong phạm vi [0, N]. Do đó, điều kiện 1 là đủ trong trường hợp này. Các điều kiện 2 và 3 chỉ là các trường hợp loại trừ.

6. Thuật toán:

   • Đọc N và K.
   • Đếm số lượng số lẻ trong mảng A (odd_count).
   • Tính số lượng số chẵn ban đầu even_count = N - odd_count.
   • Tính số lượng số lẻ mục tiêu target_odd = N - K.
   • Kiểm tra các điều kiện:
     • Nếu K % 2 != even_count % 2: In "NO".
     • Ngược lại (tính chẵn lẻ của số chẵn mục tiêu phù hợp với ban đầu):
       • Nếu even_count == 1 và K == 0: In "NO" (Số chẵn duy nhất bị kẹt không thể biến mất).
       • Ngược lại, nếu odd_count == 1 và target_odd == 0: In "NO" (Số lẻ duy nhất bị kẹt không thể biến mất).
       • Ngược lại: In "YES".

7. Ví dụ kiểm tra lại:

   • Test case 1: 4 2, [1 2 3 5]. N=4, K=2.

     • Số lẻ: 1, 3, 5 (odd_count = 3). Số chẵn: 2 (even_count = 1).
     • Mục tiêu K=2. target_odd = 4 - 2 = 2.
     • Kiểm tra bất biến: K % 2 == even_count % 2 -> 2 % 2 == 1 % 2 -> 0 == 1. Sai. In "NO". (Đúng với Output ví dụ).

   • Test case 2: 4 2, [8 5 1 3]. N=4, K=2.

     • Số lẻ: 5, 1, 3 (odd_count = 3). Số chẵn: 8 (even_count = 1).
     • Mục tiêu K=2. target_odd = 4 - 2 = 2.
     • Kiểm tra bất biến: K % 2 == even_count % 2 -> 2 % 2 == 1 % 2 -> 0 == 1. Sai. Theo logic bất biến đơn thuần thì sẽ là NO.
     • Tuy nhiên, ví dụ này lại ra YES. Điều này mâu thuẫn với phân tích bất biến dựa trên quy tắc "A_i + A_j là chẵn". Ví dụ giải thích có đề cập đến kết quả 5.5, cho thấy có thể thao tác được cả với số chẵn và số lẻ, và kết quả không nhất thiết là số nguyên, và 5.5 được coi là chẵn. Nếu tin vào ví dụ, phân tích bất biến ban đầu bị sai.

   • Giả định khác dựa trên ví dụ 2: Nếu có thể kết hợp số chẵn và số lẻ, và kết quả .5 được coi là chẵn, thì việc kết hợp E + O làm số lượng chẵn tăng 1, số lượng lẻ giảm 1. Điều này làm tính chẵn lẻ của số lượng số chẵn/lẻ bị ĐẢO NGƯỢC.

     • Nếu ban đầu có ít nhất 1 chẵn và ít nhất 1 lẻ (0 < odd_count < N), ta có thể thực hiện E+O. Điều này cho phép ta "lật" tính chẵn lẻ của số chẵn/lẻ bất cứ khi nào cần. Do đó, mọi số lượng K đều có thể đạt được trong khoảng [0, N].
     • Nếu ban đầu toàn chẵn (odd_count == 0), chỉ có thể E+E. Số chẵn chỉ thay đổi 0 hoặc -2. Tính chẵn lẻ của số chẵn không đổi (luôn chẵn). K phải là số chẵn.
     • Nếu ban đầu toàn lẻ (odd_count == N), chỉ có thể O+O. Số chẵn chỉ thay đổi 0 hoặc +2. Tính chẵn lẻ của số chẵn không đổi (luôn chẵn). K phải là số chẵn.

   • Logic dựa trên giả định ví dụ 2:

     • Đếm odd_count.
     • Nếu odd_count == 0 hoặc odd_count == N: In "YES" nếu K là số chẵn, ngược lại "NO".
     • Nếu 0 < odd_count < N: In "YES" (bất kỳ K nào trong khoảng [0,N] đều có thể đạt được).

   • Kiểm tra lại với logic này:

     • Test case 1: 4 2, [1 2 3 5]. N=4, K=2. odd_count = 3. 0 < 3 < 4. Logic nói YES. Output ví dụ là NO. Vẫn mâu thuẫn.

   • Sự mâu thuẫn giữa quy tắc được viết và ví dụ giải thích khiến bài toán khó hiểu. Tuy nhiên, trong các bài tập lập trình cạnh tranh, quy tắc về bất biến chẵn lẻ là rất phổ biến. Khả năng cao là quy tắc "A_i + A_j là chẵn" là đúng, và ví dụ giải thích có thể có lỗi diễn đạt (ví dụ 5.5 có thể được coi là "chẵn" trong một định nghĩa không chuẩn, hoặc cặp số 8 và 3 trong ví dụ không thực sự được ghép theo quy tắc).

   • Giả sử quy tắc "A_i + A_j là chẵn" là đúng và kết quả là số nguyên có tính chẵn lẻ chuẩn. Bất biến về tính chẵn lẻ của số lượng chẵn/lẻ vẫn đúng. Các trường hợp đặc biệt về số lượng 1 cũng vẫn đúng. Logic ban đầu (từ bước 6) là khả dĩ nhất nếu bỏ qua sự khó hiểu của ví dụ 2.
   • Tại sao logic ban đầu lại cho ra NO cho ví dụ 2 trong khi output là YES? Có thể có một cách khác để đạt được mục tiêu mà không chỉ dựa vào bất biến tính chẵn lẻ?

   • Quay lại logic ban đầu (từ bước 6), nó phù hợp với ví dụ 1. Hãy tin rằng logic đó là đúng và ví dụ 2 có sai sót hoặc một ngoại lệ rất đặc biệt không được mô tả rõ.

   • Chốt lại hướng giải dựa trên bất biến tính chẵn lẻ và trường hợp cố định:

     1. Đếm số lượng số lẻ ban đầu (odd_count).
     2. Tính số lượng số chẵn ban đầu (even_count = N - odd_count).
     3. Kiểm tra xem tính chẵn lẻ của số chẵn mục tiêu K có khớp với tính chẵn lẻ của số chẵn ban đầu even_count không: K % 2 == even_count % 2.
     4. Nếu tính chẵn lẻ không khớp, in ra "NO".
     5. Nếu tính chẵn lẻ khớp:
        • Kiểm tra trường hợp số chẵn duy nhất bị kẹt: Nếu even_count == 1 và mục tiêu là 0 số chẵn (K == 0), in ra "NO".
        • Kiểm tra trường hợp số lẻ duy nhất bị kẹt: Nếu odd_count == 1 và mục tiêu là 0 số lẻ (N - K == 0), in ra "NO".
        • Trong tất cả các trường hợp còn lại (tính chẵn lẻ khớp và không rơi vào 2 trường hợp bị kẹt), in ra "YES".

   • Logic này: YES if (K % 2 == (N - odd_count) % 2) AND (even_count != 1 OR K != 0) AND (odd_count != 1 OR N-K != 0). Otherwise NO.

   • Đây là hướng tiếp cận phổ biến cho các bài toán dạng này.

Hướng dẫn C++ ngắn gọn:

1. Đọc đầu vào: Đọc số lượng test case T. Vòng lặp T lần.
2. Trong mỗi test case:
   • Đọc N và K.
   • Khởi tạo biến đếm số lẻ odd_count = 0.
   • Vòng lặp N lần để đọc các phần tử của mảng A. Trong khi đọc, kiểm tra tính chẵn lẻ của mỗi phần tử: nếu là số lẻ, tăng odd_count.
   • Tính số lượng số chẵn ban đầu: even_count = N - odd_count.
   • Tính số lượng số lẻ mục tiêu: target_odd = N - K.
3. Kiểm tra điều kiện và in kết quả:
   • Sử dụng các điều kiện từ bước 5/6 của phân tích (dựa trên bất biến và trường hợp cố định):
     • Nếu K % 2 != even_count % 2: In "NO".
     • Ngược lại (K và even_count cùng tính chẵn lẻ):
       • Nếu even_count == 1 và K == 0: In "NO".
       • Ngược lại, nếu odd_count == 1 và target_odd == 0: In "NO".
       • Ngược lại (tính chẵn lẻ khớp và không bị kẹt ở 0): In "YES".
4. Đảm bảo hiệu suất: Việc đếm số lẻ là O(N) cho mỗi test case. Tổng N trên tất cả các test case không vượt quá 10^6 đảm bảo giải pháp này chạy trong thời gian cho phép.

Làm thêm nhiều bài tập miễn phí tại đây