題意#
題目給定工廠內有 \( n \) 台獨立運作的機器，需生產 \( k \) 件產品。
每台機器製造單件產品的時間不同，皆可同時運作。
我們需要求出完成 \( k \) 件產品所需的最少總時間。
思路#
「求最短時間」且「時間越長產品越多」具有單調性，適用「對答案進行二分搜（Binary Search on Answer）」的技巧。
若設定可用時間為 \( m \) 秒，計算此時間內總共能生產多少產品：
每台機器在 \( m \) 秒內的產量即為 \( m \) 除以其製造單件產品的時間。
將所有機器的產量加總，即可得知 \( m \) 秒的總產能。
- 若總產量達到或超過目標 \( k \)，代表 \( m \) 秒可行，記錄為暫時的最佳解並嘗試縮小時間（縮小右界）。
- 若總產量未達 \( k \)，代表 \( m \) 秒不足，需增加時間（提高左界）。
二分搜的下界為 \( 0 \)，上界為「把所有工作交給最快的機器單獨完成」所需的時間。
在上下界間進行搜尋，即可找出最短時間。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, k; cin >> n >> k;
vector<int> v(n);
for (auto &i : v) cin >> i;
// l 為下界 0 ； r 為上界（最快的機器單獨做完 k 件的時間）； ans 紀錄符合條件的最短時間
int l = 0, r = *min_element(all(v))*k+1, ans = -1;
while (l < r) {
// m 為這次猜測的可用時間
int m = l+((r-l)>>1), amount = 0;
// 加總所有機器在 m 秒內的各自產量
for (auto &i : v) amount += m/i;
// 若產量達標，將其設為暫時解答並嘗試縮短時間
if (amount >= k) ans = r = m;
// 產量不夠，必須增加時間
else l = m+1;
}
// 輸出最少需要的總時間
cout << ans << '\n';
}
