Максимизируйте сумму массива, выбирая пары и разделив одну часть и умножив другую на K
Учитывая массив 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)