Ctrl K

Самые дешёвые свободные номера

Средняя
Массив taken содержит уже занятые номера (положительные целые, возможны повторы). Нужно выдать ещё count новых номеров: все они должны быть разными положительными целыми числами и не встречаться в taken. Выберите номера так, чтобы их сумма была наименьшей, и верните эту сумму. Заметьте, что count может быть очень большим, так что перебирать номера по одному не получится.
Пример 1
taken=[2, 5, 3], count=3 → 11

Свободны 1, 4, 6, 7, … Берём три наименьших: 1 + 4 + 6 = 11.

Пример 2
taken=[100, 100], count=4 → 10

Числа 1, 2, 3, 4 свободны, их сумма 10. Повтор в taken ничего не меняет.

Пример 3
taken=[1, 2, 3], count=2 → 9

Первые три числа заняты, берём 4 и 5: сумма 9.

Ограничения
  • 1 ≤ len(taken) ≤ 10⁵
  • 1 ≤ taken[i] ≤ 10⁹
  • 1 ≤ count ≤ 10⁸
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПодтянуть или опустить СредняяОкруглить цены до нужной суммы СредняяСредний мешок СредняяЦена тает с каждой продажей СредняяОдни призы, разные вкусы Средняя
загружаем Python…
Вход
taken=[2, 5, 3], count=3
Ожидается
11

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