Максимизируйте сумму max и min каждого из K массивов, полученных путем деления данного массива на заданные размеры

Даны два массива: arr[] размера N и div[] размера K . Разделите arr[] на K различных массивов, каждый из которых имеет размер div[i] . Задача состоит в том, чтобы найти общую сумму после максимизации суммы максимума и минимума каждого разделенного массива.

Примеры:

Input: arr[] = {3, 1, 7, 4}, div[] = {1, 3}, N = 4, K = 2
Output: 19
Explanation: Divide the array in the following way:

• {7}, sum of maximum and minimum = (7 + 7) = 14
• {1, 3, 4}, sum of maximum and minimum = (4 + 1) = 5

Total sum = 14 + 5 = 19.

Input: arr[] = {10, 12, 10, 12, 10, 12}, div[] = {3, 3}, N = 6, K = 2
Output: 44

Подход: выполните следующие шаги, чтобы решить проблему:

1. Возьмите переменную, скажем, count1 , чтобы подсчитать количество единиц в div[] .
2. Отсортируйте оба массива, arr[] в порядке убывания и div[] в порядке возрастания .
3. Возьмите переменную, скажем, ans , чтобы сохранить ответ, и другую переменную, скажем, t , которая представляет, с какого индекса должна быть запущена итерация в div[] .
4. Итерируйте массив до K , на каждой итерации добавляйте элементы в ans и снова добавляйте этот элемент в ans , пока count1 больше 0 , потому что массивы размера 1 имеют один и тот же элемент как максимум и минимум .
5. Снова повторите цикл от K -го индекса до конца массива. Добавьте элемент в ans и обновите индекс.
6. Верните ответ .

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

Временная сложность: O(NlogN), время, необходимое для сортировки
Вспомогательное пространство: O(1)