Ctrl K

Растущие группы без повторов

Сложная
Дан массив limits длины n. Из чисел от 0 до n - 1 нужно составить несколько групп так, чтобы: - внутри одной группы числа не повторялись; - каждая следующая группа была строго длиннее предыдущей; - число i встречалось во всех группах вместе не больше limits[i] раз. Верните наибольшее количество групп, которое удастся составить.
Пример 1
limits=[3, 1, 2] → 3

Группы [0], [0, 2], [0, 1, 2]: число 0 использовано трижды, 1 — один раз, 2 — дважды, размеры растут 1 → 2 → 3.

Пример 2
limits=[1, 1, 1, 1] → 2

Каждое число доступно один раз, поэтому подойдут, например, [0] и [1, 2]. На третью группу из трёх чисел остаётся только число 3.

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

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