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

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

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

  • Выберите два индекса, i и j , где arr[i] должен быть кратным K .
  • Сделать arr[i] = arr[i]/K и arr[j] = K*arr[j]
  • После выполнения вышеуказанных операций сумма элементов массива должна быть максимальной.

Примеры:

Input: arr[] = {6, 6, 3}, N = 3, K = 3
Output: 57
Explanation:  The optimal sequence for which sum of the array elements would be maximized is:

  • Take i = 0 and j = 1, arr[0] = arr[0]/3 = 2, arr[1] = arr[1]*3 = 18, now the new array becomes, [2, 18, 3]
  • Take i = 2 and j = 1, arr[2] = arr[2]/3 = 1, arr[1] = arr[1]*3 = 54, the array becomes [2, 54, 1]

Sum = 2 + 54 + 1 = 57

Input: arr[] = {1, 2, 3, 4, 5}, N = 5, K = 2
Output: 46
Explanation: The operation performed is:
Take i = 1 and j = 4, arr[1] = arr[1]/2 = 1, arr[4] = arr[4]*2 = 10. Now arr[] = {1, 1, 3, 4, 10}. 
Take i = 3 and j = 4, arr[3] = arr[3]/2 = 2, arr[4] = arr[4]*2 = 20. Now arr[] = {1, 1, 3, 2, 20}.
Take i = 3 and j = 4, arr[3] = arr[3]/2 = 1, arr[4] = arr[4]*2 = 40. Now arr[] = {1, 1, 3, 1, 40}
Sum = 1 + 1+ 3 + 1 + 40 = 46.

Подход: жадный подход состоит в том, чтобы разделить все элементы массива, кратные K , на K и подсчитать общее количество выполненных операций деления (скажем, X ). Затем отсортируйте массив и умножьте максимальный элемент массива X раз на K , т.е. arr[N-1] = arr[N-1]*K X . Выполните следующие шаги, чтобы решить эту проблему:

  • Создайте переменную total_division = 0 для хранения общего количества выполненных делений.
  • Переберите диапазон [0, N), используя индекс переменной, и выполните следующие задачи:
    • Если arr[index] %K = 0 , то узнайте, сколько раз можно разделить arr[index] на K , и столько же раз увеличьте total_division .
  • Отсортируйте массив arr[] .
  • Запустите цикл while, пока total_division > 0 , и сделайте arr[N-1] = arr[N-1] * K и уменьшите total_division.
  • Создайте переменную max_sum = 0.
  • Переберите диапазон [0, N), используя индекс переменной, и выполните следующие задачи:
    • Обновить max_sum += arr[index] .
  • После выполнения вышеуказанных шагов выведите значение max_sum в качестве ответа.

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


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

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