Factory Machines
A factory has \(n\) machines that can make products. The \(i\)-th machine needs \(k_i\) seconds to make one product. The machines work at the same time, and each of them can make any number of products.
Find the minimum time needed to make \(t\) products.
Constraints:
- \(1 \le n \le 2 \cdot 10^5\)
- \(1 \le t \le 10^9\)
- \(1 \le k_i \le 10^9\)
Input:
- First line: two integers \(n\) and \(t\) — the number of machines and the number of products.
- Second line: \(n\) integers \(k_1, k_2, \dots, k_n\).
Output:
- One integer — the minimum time.
Example:
Input:
3 7
3 2 5
Output:
8
(In \(8\) seconds the machines make \(2\), \(4\), and \(1\) products.)
Solution
In \(T\) seconds the \(i\)-th machine makes \(\lfloor T / k_i \rfloor\) products, so all machines together make
\[ \sum_{i=1}^{n} \left\lfloor \frac{T}{k_i} \right\rfloor \]
products. We call a time \(T\) enough if this sum is at least \(t\).
If \(T\) is enough, then every larger time is also enough. So the times that are not enough are followed by the times that are enough:
T: 1 2 3 4 5 6 7 8 9 ...
enough: no no no no no no no yes yes ...
The answer is the first time that is enough. This is the same search as in the lesson, where we looked for the first element greater than or equal to \(X\). Here we do not search in an array. We search in the range of possible answers, and instead of the condition arr[mid] >= x we call a function enough(mid). This technique is called binary search on the answer.
The range of the search:
- The answer is at least \(1\).
- The fastest machine alone makes \(t\) products in \(\min(k_i) \cdot t \le 10^{18}\) seconds, so this time is always enough.
Each call of enough takes \(O(n)\) time, and the binary search makes about \(\log_2 10^{18} \approx 60\) calls, so the whole solution takes \(O(n \log (\min(k_i) \cdot t))\) time.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
long long t;
vector<long long> k;
// can the machines make t products in `time` seconds?
bool enough(long long time) {
long long products = 0;
for (int i = 0; i < n; i++) {
products += time / k[i];
if (products >= t) {
return true; // stop early, so that products does not overflow
}
}
return false;
}
int main() {
cin >> n >> t;
k.resize(n);
for (int i = 0; i < n; i++) {
cin >> k[i];
}
// the fastest machine alone makes t products in this time
long long left = 1;
long long right = *min_element(k.begin(), k.end()) * t;
long long answer = right;
while (left <= right) {
long long mid = left + (right - left) / 2;
if (enough(mid)) {
answer = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << answer << "\n";
}- The times reach \(10^{18}\), so use
long long. - The sum of the products can be much greater than \(10^{18}\) and overflow
long long. The functionenoughstops as soon as the sum reaches \(t\). left + (right - left) / 2is equal to(left + right) / 2, butleft + rightcan overflow when both are close to \(10^{18}\).