Problem
All machines start at time 0 and work independently. A machine with time t finishes one item after t seconds, another after 2t seconds, and so on. Find the earliest whole second when their combined production reaches the target.
Implement factory_machines(times, target).
Input
times: Seconds needed for one item on each machine.
target: The number of completed items required.
Output
Return the minimum elapsed seconds.
Einschränkungen
1 ≤ machines ≤ 200,000. Each time and the target are between 1 and 1,000,000,000. The answer fits signed 64-bit.
Beispiele
Eingabe:
times = [2, 3]
target = 5
Erwartete Ausgabe:
expected = 6Eingabe:
std::vector<long long> times = {2, 3};
long long target = 5;
Erwartete Ausgabe:
long long expected = 6;Eingabe:
long[] times = new long[] {2, 3};
long target = 5;
Erwartete Ausgabe:
long expected = 6;Erläuterung
At time 6 the machines have made 3 + 2 = 5 items. At time 5 they have made only 2 + 1 = 3.
Eingabe:
times = [4]
target = 3
Erwartete Ausgabe:
expected = 12Eingabe:
std::vector<long long> times = {4};
long long target = 3;
Erwartete Ausgabe:
long long expected = 12;Eingabe:
long[] times = new long[] {4};
long target = 3;
Erwartete Ausgabe:
long expected = 12;Erläuterung
One machine completes its third item at 3 × 4 = 12 seconds.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
For any chosen time, you can count how many items all machines together would finish by then.
Hinweis 2
The answer is the earliest time where that produced count reaches the target.
Hinweis 3
A monotonic condition like this is well suited to searching over time instead of simulating production.
Erwartete Komplexität
O(n log T) time, O(1) extra space
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.