Минимизировать сумму абсолютных разностей элементов с одинаковым индексом двух заданных массивов не более чем одной заменой

Для заданных двух массивов A[] и B[] размера N каждый задача состоит в том, чтобы найти минимально возможную сумму абсолютной разности одинаковых индексированных элементов двух массивов, т.е. сумму |A[i] – B[i]| для всех i таких, что 0 ≤ i < N , путем замены не более одного элемента в A[] другим элементом A[] .

Примеры:

Input: A[] = {6, 4, 1, 9, 7, 5}, B[] = {3, 9, 7, 4, 2, 1}, N = 6
Output: 22
Explanation: Replace A[2] with A[4]. The array A[] modifies to [6, 4, 7, 9, 7, 5]. This yields an absolute sum difference of |6 – 3| + |4 – 9| + |7 – 7| + |9 – 4| + |7 – 2| + |5 – 1| = 22, which is maximum possible.

Input: A[] = {2, 5, 8}, B[] = {7, 6, 1}, N = 3
Output: 7

Подход: Идея решения проблемы состоит в том, чтобы вычислить для каждого B[i] (0 ≤ i < N) ближайший элемент в A[] к B[i] с помощью двоичного поиска и выбрать лучший вариант.
Выполните следующие действия, чтобы решить проблему.

1. Инициализируйте два массива diff[] и BestDiff[] размера N .
2. Инициализируйте переменную sum равным 0 .
3. Перейдите от 0 к N – 1 и для каждого i сохраните diff[i]= abs(A[i] – B[i]) и добавьте diff[i] к sum .
4. Отсортируйте массив A[] в порядке возрастания.
5. Перебрать индексы от 0 до N – 1 и для каждого i , используя двоичный поиск, найти элемент в A[] , ближайший к B[i] , скажем X , и сохранить его в BestDiff[] как BestDiff[i] = abs (Б[и] – Х)
6. Инициализируйте переменную BestPick .
7. Перебрать индексы от 0 до N – 1 и обновить BestPick как BestPick = max(BestPick, diff[i]-BestDiff[i])
8. Теперь Sum – BestPick дает ответ.

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

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