Разделить массив на максимально возможные подмножества, произведение их длины на максимальный элемент не менее K

Опубликовано: 21 Сентября, 2022

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

Примеры:

Input: N = 5, K = 4, arr[] = {1, 5, 4, 2, 3}
Output: 3
Explanation:
The array can be split into 3 possible subsets {1, 2}, {4, 3} and {5}, whose product of maximum element of the subsets with its size is at least K(= 4). Therefore, the count of such subsets is 3.

Input: N = 4, K = 81, arr[] = {12, 8, 14, 20}
Output: 0

Подход: Данную проблему можно решить, заметив тот факт, что элементы, число которых не меньше K , могут сами по себе образовывать подходящую группу. Чтобы извлечь максимальное количество групп, в которых нет элементов больше, чем равных K , идея состоит в том, чтобы начать включать элементы с минимального элемента массива arr[] , а затем продолжать двигаться к более крупным элементам, пока не будет подходящей группы. сформировался. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную, скажем, count как 0 , которая хранит результирующее количество подмножеств, и pre как 1 , чтобы сохранить начальный размер группы.
  • Отсортируйте заданный массив arr[] в порядке возрастания.
  • Переберите диапазон [0, N], используя переменную, скажем i , и выполните следующие шаги:
    • Если значение arr[i] * pre равно как минимум K , тогда увеличьте значение count на 1 и установите значение pre равным 1 .
    • В противном случае увеличьте значение pre на 1 .
  • После выполнения вышеуказанных шагов выведите значение count как результирующее количество подмножеств.

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ