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

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

Дан массив положительных целых чисел arr[] и число K . задача состоит в том, чтобы максимизировать сумму массива, заменив любые K элементов массива, взяв модуль с любым положительным целым числом, которое меньше, чем arr[i] , т.е. (arr[i] = arr[i]%X, где X ≤ обр [и]).

Примеры:

Input: arr[] = {5, 7, 18, 12, 11, 3}, K = 4
Output: 41
Explanation: The replacement should be {5%3, 7%4, 18, 12, 11%6, 3%2}

Input: arr[] = {8, 2, 28, 12, 7, 9}, K = 4
Output: 55
Explanation: The replacement should be {8%5, 2%2, 28, 12, 7%4, 9}

Подход: для каждого элемента arr[i] в массиве arr[] модуль его с (arr[i]/2 +1) , который даст максимально возможное значение arr[i] после операции. Ниже приведены шаги для решения проблемы

  • Отсортируйте массив arr[] .
  • Перебрать диапазон [0, K), используя переменную i , и выполнить следующие задачи:
    • Для каждого элемента arr[i] задайте модуль (arr[i]/2 +1) и обновите результат.
  • Найдите сумму обновленного массива и выведите ее.

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


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

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