Максимизируйте сумму средних значений пар, сделанных с использованием элементов X [] и Y []

Даны два массива X[] и Y[] длины N каждый. Вы можете составить пару, выбрав ровно один элемент из X[] и Y[]. Задача состоит в том, чтобы найти максимальную сумму средних, составив N пар.

Примеры:

Input: N = 3, X[] = {6, 5, 4}, Y[] = {3, 1, 2}
Output: 10
Explanation: One of the possible way to arrange pairs is: (4, 2) (5, 1) (6, 3), Which gives average as ((4 + 2) / 2),  ((1 + 5) / 2), ((6 + 3) / 2), Which is equal to 3, 3 and 4 respectively. Total sum of average is: 3 + 3 + 4 = 10. Which is maximum possible.

Input: N = 5, X[] = {4, 8, 3, 2, 1}, Y[] = {2, 5, 1, 2, 3}
Output: 15
Explanation: It can be verified that no other arrangement of pairs give sum of average more than 15.

Подход: Реализуйте идею ниже, чтобы решить проблему:

The problem can be solved via counting number of odd elements present in X[] and Y[]. Formula for calculating maximum possible average will be: (Total sum of elements of X[] and Y[] – Absolute difference(count of odd elements in X[] – count of odd elements in Y[])) / 2.

The second term is subtracted because there will be that many pairs where one element is odd and the other is even. And in case of each such pair we lose the value equal to 0.5 from the sum of averages.

Иллюстрация подхода:

Consider an example: N = 5, X[] = {4, 8, 3, 2, 1}, Y[] = {2, 5, 1, 2, 3}

• Total sum of elements of X[] = 4 + 8 + 3 + 2 + 1 = 18
• Total sum of elements of Y[] = 2 + 5 + 1 + 2 + 3 = 13
• Total sum of both arrays = 18 + 13 = 31
• Count of odd elements in X[] = 2(3, 1)
• Count of odd elements in Y[] = 3(5, 1, 3) 
• Total average of pairs will be: 
  (total sum of both arrays – absolute difference(odd count of X[] – odd count of Y[]))/2 = (31 – |2 – 3|) / 2 = (31 – 1) / 2 = 30 / 2 = 15.

This is the maximum possible sum of averages in this case.

Выполните шаги, указанные ниже, чтобы решить проблему:

• Получите общую сумму элементов X[] и Y[] .
• Подсчитайте количество нечетных элементов в X[] .
• Подсчитайте количество нечетных элементов в Y[] .
• Распечатайте вывод в соответствии с обсуждаемой формулой.

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

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