What is the motivation behind Binary Search in Factory Machines? I understand the approach, but how would we think of dynamically adjusting the answer (binary search) versus statically building the answer for each machine? I first thought of a greedy method when I saw this problem. In the sample input, clearly 2 must make the most products, followed by 3, and then 5. Is there a solution where we allocate a number p_i of products to each machine until the sum is at least t products – such that the maximum of k_i * p_i is minimized? Why would this not strike your mind first? What motivations (keywords, your thought process, etc.) would make you think of proving monotonicity and using binary search on this problem?
t is huge …
t is up to 1e9. That doesn’t strike my mind as “definitely Binary Search”, the way 1e18 does. I actually think of storing t as an integer value based on its bounds. I believe the following idea does that, since we only use t to compare our greedy answer with the total number of products needed.
I am not quite sure what the greedy approach would look like, though. Does it make sense to you to try greedy? I assume otherwise, so can you please elaborate on why you would motivate binary search for this problem? Thanks.
given a fixed amount of time, one can calculate the total number of products produced in \mathcal O(N).