Ctrl K

Наименьший делитель в пределах лимита

Средняя
Дан массив положительных чисел amounts и число limit. Выберем целый делитель d ≥ 1, разделим на него каждое число массива с округлением **вверх** (например, 7 / 3 даёт 3, а 10 / 2 даёт 5) и сложим результаты. Найдите наименьший d, при котором эта сумма не превышает limit. Гарантируется, что limit не меньше длины массива, поэтому подходящий делитель всегда есть.
Пример 1
amounts=[3, 8, 14], limit=5 → 7

При делителе 6 получаем 1 + 2 + 3 = 6, это больше 5. При делителе 7: 1 + 2 + 2 = 5 — подходит.

Пример 2
amounts=[6, 6], limit=12 → 1

Уже при делителе 1 сумма равна 12 — меньше делителя не бывает.

Ограничения
  • 1 ≤ len(amounts) ≤ 5·10⁴
  • 1 ≤ amounts[i] ≤ 10⁶
  • len(amounts) ≤ limit ≤ 10⁶
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПоиск в сдвинутом отсортированном массиве СредняяПервая и последняя копия СредняяПоиск в таблице-цепочке СредняяПоиск в сдвинутом массиве с повторами СредняяМинимум в сдвинутом списке Средняя
загружаем Python…
Вход
amounts=[3, 8, 14], limit=5
Ожидается
7

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 58 тестов на сервере, включая скрытые.