Все машины начинают работу в момент времени 0 и работают независимо друг от друга. Машина с временем t изготавливает одно изделие за t секунд, следующее — через 2t секунд, и так далее. Найдите минимальное целое число секунд, к которому суммарное количество произведённых изделий всеми машинами достигнет цели.
Реализуйте функцию factory_machines(times, target).
Входные данные
times: Количество секунд, необходимое каждой машине для изготовления одного изделия.
target: Требуемое количество готовых изделий.
Выходные данные
Верните минимальное количество прошедших секунд.
Ограничения
1 ≤ машин ≤ 200 000. Каждый элемент массива времени и цель — от 1 до 1 000 000 000. Ответ помещается в знаковый 64-битный тип.
Примеры
Ввод:
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;Пояснение
В момент времени 6 машины изготовили 3 + 2 = 5 изделий. В момент времени 5 они сделали только 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;Пояснение
Одна из машин завершает своё третье изделие за 3 × 4 = 12 секунд.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Для любого выбранного времени можно посчитать, сколько изделий все машины вместе успеют сделать к этому моменту.
Подсказка 2
Ответ — это самое раннее время, когда произведённое количество достигает цели.
Подсказка 3
Такая монотонная зависимость хорошо подходит для поиска по времени вместо симуляции производства.
Ожидаемая сложность
O(n log T) по времени, O(1) доп. памяти
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.