Условие
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.
Ограничения
1 ≤ machines ≤ 200,000. Each time and the target are between 1 and 1,000,000,000. The answer fits signed 64-bit.
Примеры
Ввод:
times = [2, 3]
target = 5
Ожидаемый вывод:
expected = 6Ввод:
std::vector<long long> times = {2, 3};
long long target = 5;
Ожидаемый вывод:
long long expected = 6;Ввод:
long[] times = new long[] {2, 3};
long target = 5;
Ожидаемый вывод:
long expected = 6;Пояснение
At time 6 the machines have made 3 + 2 = 5 items. At time 5 they have made only 2 + 1 = 3.
Ввод:
times = [4]
target = 3
Ожидаемый вывод:
expected = 12Ввод:
std::vector<long long> times = {4};
long long target = 3;
Ожидаемый вывод:
long long expected = 12;Ввод:
long[] times = new long[] {4};
long target = 3;
Ожидаемый вывод:
long expected = 12;Пояснение
One machine completes its third item at 3 × 4 = 12 seconds.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
For any chosen time, you can count how many items all machines together would finish by then.
Подсказка 2
The answer is the earliest time where that produced count reaches the target.
Подсказка 3
A monotonic condition like this is well suited to searching over time instead of simulating production.
Ожидаемая сложность
O(n log T) time, O(1) extra space
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.