Problem
Alle Maschinen starten bei Zeit 0 und arbeiten unabhängig voneinander. Eine Maschine mit Zeit t stellt ein Produkt nach t Sekunden fertig, das nächste nach 2t Sekunden, und so weiter. Finde die früheste ganze Sekunde, zu der ihre kombinierte Produktion das Ziel erreicht.
Implementiere factory_machines(times, target).
Eingabe
times: Sekunden, die jede Maschine für ein Produkt benötigt.
target: Die benötigte Anzahl fertiger Produkte.
Ausgabe
Gib die minimale verstrichene Zeit in Sekunden zurück.
Einschränkungen
1 ≤ Maschinen ≤ 200.000. Jede Zeit und das Ziel liegen zwischen 1 und 1.000.000.000. Die Antwort passt in einen vorzeichenbehafteten 64-Bit-Wert.
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
Nach 6 Sekunden haben die Maschinen 3 + 2 = 5 Produkte hergestellt. Nach 5 Sekunden sind es nur 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
Eine Maschine stellt ihr drittes Produkt nach 3 × 4 = 12 Sekunden fertig.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Für eine gewählte Zeit kannst du zählen, wie viele Teile alle Maschinen zusammen bis dahin fertiggestellt hätten.
Hinweis 2
Die Antwort ist die früheste Zeit, zu der diese produzierte Anzahl das Ziel erreicht.
Hinweis 3
Eine monotone Bedingung wie diese eignet sich gut für eine Suche über die Zeit statt für eine Simulation der Produktion.
Erwartete Komplexität
Zeit O(n log T), zusätzlicher Speicher O(1)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.