Максимизируйте сумму массива, сформированную путем добавления пары элементов

Дан массив a[] из 2*N целых чисел. Задача состоит в том, чтобы сделать массив a[] размера N , т.е. уменьшив его вдвое, так что a[i] = ⌊(a[j] + a[k ]) / N⌋ , 0 < j, k < 2*N – 1 . и сформируйте массив так, чтобы сумма всех элементов массива a[] была максимальной. Выведите максимальную сумму.

Примеры :

Input: arr[] = {3, 5, 10, 8, 4, 7}, N = 3
Output: 12
Explanation: If we form, a[] = {4 + 5, 7+8, 3+10} = {9, 15, 13}, 
Sum = floor(9/3) + floor(15/3) + floor(13/3) = 3 + 5 + 4 = 12.

Input: arr[] = {1, 2}, N = 1
Output: 3

Подход : Чтобы решить проблему, следуйте следующей идее:

The idea is to pair the elements whose sum (a[i]+a[j])%N > a[i]%N + a[j]%N, for this we have to store a[i]/N for 0<i<2*N-1 and modify a[i] = a[i]%N for finding the remainder. Now we have to from i with j such that a[i] + a[j] >= N [0<(a[i]+a[j])<2N-2], because, we have to take as many extra count that we were loosing with floor division. 

For this we have to sort the array and initialize pointers i = 2*N-1and  j=0, and start forming pairs with last element because it is the greatest, if it cannot form pair with sum ≥ N then any other pair does not form, we have to from the pairs of available largest element with smallest element such that sum ≥ N if possible.

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

• Прежде всего, мы должны сохранить сумму данного массива как sum=sum+arr[i]/n и обновить значение массива как arr[i]=arr[i]%n.
• После этого отсортируйте массив.
• Затем, используя метод двух указателей, найдите пары, сумма которых больше или равна n.
• Затем верните сумму.

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

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

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам
• Техника двух указателей