In this problem, you're given $n$ machines and asked the minimum time these machines need to work to create $t$ products such that the $i$-th machine creates a product in $k_i$ time.

Binary Search

Observe that the time needed to create at least $x$ products is monotonic. In other words, if the given machines can create $x$ products in $y_1$ time, then the same machines can create at least $x$ products in $y_2>y_1$ time. Using this property, we can binary search over the answer. Read this module for more information.

For some value we binary search for, $ans$, we are left with the task of checking whether we can create $t$ products in $ans$ time. To do this, observe that it's optimal for every machine to work simultaneously. Then, in $ans$ time, machine $i$ can create $\lfloor \frac{ans}{k_i}\rfloor$ products.

Overall, the $n$ machines can create ‎‎${\sum }_{i=1}^n\lfloor \frac{ans}{k_i}\rfloor$ products. If this sum $\ge t$, then $ans$ is valid.

1#include <bits/stdc++.h>
2using namespace std;
3using ll = long long;
4using vi = vector<int>;
5#define pb push_back
6#define rsz resize
7#define all(x) begin(x), end(x)
8#define sz(x) (int)(x).size()
9using pi = pair<int,int>;
10#define f first