Ctrl K

Разбить на возрастающие цепочки

Сложная
Дан массив values, отсортированный по неубыванию, и число min_len. Нужно разложить все элементы массива по нескольким цепочкам так, чтобы: - каждый элемент попал ровно в одну цепочку (порядок элементов внутри цепочки — как в массиве); - внутри каждой цепочки значения строго возрастали; - в каждой цепочке было не меньше min_len элементов. Верните True, если такое разбиение существует, и False иначе.
Пример 1
values=[2, 3, 3, 5, 5, 8], min_len=3 → True

Троек две, поэтому цепочек нужно хотя бы две; из 6 элементов обе можно сделать длины 3: [2, 3, 5] и [3, 5, 8].

Пример 2
values=[4, 4, 4, 6, 7], min_len=2 → False

Три четвёрки должны попасть в три разные цепочки, и каждой нужно хотя бы 2 элемента — это 6 элементов, а их всего 5.

Пример 3
values=[1, 9], min_len=1 → True
Ограничения
  • 1 ≤ min_len ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁵
  • values отсортирован по неубыванию
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОтрезки ровно с k видами СложнаяРазличные НОД наборов СложнаяРавные разрезы после одной замены СложнаяПопулярность префиксов СложнаяРазвести совпадающие карточки Сложная
загружаем Python…
Вход
values=[2, 3, 3, 5, 5, 8], min_len=3
Ожидается
True

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