Максимизируйте сумму массива после увеличения не более чем K элементов с последующим делением массива на X

Учитывая массив, arr[] и два целых числа, K и X, задача состоит в том, чтобы максимизировать сумму элементов массива после не более чем K приращений любых элементов, а затем разделить все элементы на X

Пример:

Input: arr = {16, 15, 17}, K = 8, X = 10
Output: 5
Explanation: At most 8 increments are allowed. So, increment element at index 0 by 4 and element at index 2 by 3. So the modified array becomes {20/10, 15/10, 20/10} = {2, 1, 2}, therefore the sum is 2+1+2 = 5

Input: arr = {8, 13, 2, 4, 7}, K = 6, X = 5
Output: 7

Подход: Данная проблема может быть решена с использованием жадного подхода. Идея состоит в том, чтобы отсортировать массив, настроив компаратор таким образом, чтобы элементы, которые требуют наименьшего приращения, чтобы стать делимыми на X , встречались первыми. Выполните следующие шаги, чтобы решить проблему:

• Отсортируйте ArrayList в том порядке, в котором элементы, имеющие больший остаток после деления на X , встречаются первыми.
• Итерируйте ArrayList и на каждой итерации:
  • Найдите оставшееся значение rem , которое нужно добавить к arr[i], чтобы оно стало кратным X
    • Если K < rem, то разорвать цикл
    • Иначе увеличить arr[i] на rem и уменьшить K на rem
• Инициализировать переменную сумму до 0
• Пройдите по ArrayList и на каждой итерации:
  • Добавить arr[i] / X к сумме

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

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