Проверить, можно ли данный массив разделить на подпоследовательности K, увеличивающие последовательные целые числа

Учитывая массив arr[] из N целых чисел и положительное целое число K , задача состоит в том, чтобы проверить, возможно ли разделить массив на возрастающие подпоследовательности из K последовательных целых чисел, так что каждый элемент может вносить вклад только в одну подпоследовательность.

Пример :

Input: arr[] = {1, 2, 1, 3, 2, 3}, K = 3
Output: Yes
Explanation: The given array can be divided as {1, 2, 1, 3, 2, 3} => {1, 2, 3} and {1, 2, 1, 3, 2, 3} => {1, 2, 3}. Both subsequences have 3 consecutive integers in increasing order.

Input: arr[] = {4, 3, 1, 2}, K = 2
Output: No

Подход: Вышеупомянутая проблема может быть решена с помощью жадного подхода с использованием бинарного поиска. Можно заметить, что для любого целого числа arr[i] наиболее оптимальным выбором является выбор наименьшего индекса arr[i] + 1 в подмассиве arr[i+1, N) . Используя это наблюдение, выполните следующие шаги, чтобы решить данную проблему:

• Если K не является делителем N , возможное множество требуемых подпоследовательностей не существует. Следовательно, напечатайте № .
• Сохраните индексы каждого целого числа в структуре данных Set. Его можно эффективно хранить с помощью карты, имеющей структуру пары «ключ-набор».
• Поддерживайте посещаемый массив, чтобы отслеживать индексы, которые уже включены в подпоследовательность.
• Выполните итерацию для каждого i в диапазоне [0, N), и если целое число по текущему индексу еще не посещалось, выполните следующие шаги:
  • Используя функцию upper_bound, найдите наименьший индекс arr[i] + 1 в диапазоне [i+1, N) и обновите с его помощью значение последнего элемента текущей подпоследовательности.
  • Повторяйте вышеупомянутый шаг K-1 количество раз, пока не будет создана полная подпоследовательность из K целых чисел.
• Во время любой итерации, если требуемое целое число не существует, не существует возможного набора требуемых подпоследовательностей. Следовательно, напечатайте № . В противном случае выведите Да .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N * log N)
Вспомогательное пространство: O(N)