問題描述

工廠有 $n$ 台機器，可以用來製造產品。你的目標是製造總共 $t$ 個產品

每台機器需要的時間不同，你知道每台機器製造一個產品所需的秒數

所有機器可以同時工作，你也可以自由安排它們的工作時間表

請計算：最短需要多少時間，才能製造出 $t$ 個產品

二分搜

像這種題目：某個條件下，時間越長越容易成功（或反過來）

可以定義一個 $check(time)$ 函數，來判斷「在這個時間內是否可行」

如此我們可以不斷二分搜限縮範圍，直到找到最小的時間

二分搜的區間

常見做法有左閉右開跟左閉右閉，我在寫這題的時候就搞混這兩種

左閉右開

while (left < right) {
    int mid = left + (right - left) / 2;
    if (/*答案在左邊*/) {
        right = mid;
    } else {
        left = mid + 1;
    }
}
return left;

左閉右閉

while (left <= right) {
    ll mid = (left + right) / 2;
    if (/*答案在左邊*/) {
        ans = mid;
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}
return ans;

練習題

CSES - Factory Machines

連結：https://cses.fi/problemset/task/1620

求最小製作完 $t$ 個產品的時間，答案的範圍是 [1, 最快的機器 * t]

我們只要在這個範圍二分搜即可

完整程式碼

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

bool solve(ll mid, ll N, ll T, int* Machine) {
    ll product = 0;
    for (int i = 0; i < N; i++) {
        product += mid / Machine[i];
        if (product >= T) return true;
    }
    return false;
}

ll bs(ll N, ll T, int* Machine) {
    ll left = 1, right = *(min_element(Machine, Machine + N)) * T;
    ll ans = INT_MAX;
    while (left < right) {
        ll mid = left + (right - left) / 2;
        if (solve(mid, N, T, Machine)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

int main() {
    ll n, t;
    cin >> n >> t;
    int machine[200005];
    for (int i = 0; i < n; i++) cin >> machine[i];
    cout << bs(n, t, machine) << "\n";
}