Минимизируйте стоимость, разделив заданный массив на подмножества размера K и добавив в стоимость самые высокие элементы K/2 каждого подмножества.

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

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

Примечание: ⌈K/2⌉ означает максимальное значение K/2.

Примеры:

Input: arr[] = {1, 1, 2, 2}, K = 2
Output: 3
Explanation: The given array elements can be divided into subsets {2, 2} and {1, 1}. 
Hence, the cost will be 2 + 1 = 3, which is the minimum possible. 

Input: arr[] = {1, 2, 3, 4, 5, 6}, K = 3
Output: 16
Explanation: The array can be split like {1, 2, 3} and {4, 5, 6}.
Now ceil(3/2) = ceil(1.5) = 2.
So take 2 highest elements from each set. 
The sum becomes 2 + 3 + 5 + 6 = 16

Подход: Данную задачу можно решить с помощью жадного подхода. Идея состоит в том, чтобы отсортировать элементы в порядке убывания и начать последовательно формировать группы из K элементов, сохраняя сумму старших ⌈K/2⌉ элементов каждой группы в переменной. Это гарантирует, что элементы, стоимость которых не учитывается, является максимально возможной, и, следовательно, минимизирует общую стоимость выбранных элементов.

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

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

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