Минимизировать сумму абсолютных значений A[i] – (B + i) для данного массива

Для заданного массива arr[ ] размера N задача состоит в том, чтобы найти минимально возможное значение выражения abs(arr[1] – (b + 1)) + abs(arr[2] – (b + 2)) . . . abs(arr[N] – (b + N)) , где b — независимое целое число.

Input: arr[ ] = { 2, 2, 3, 5, 5 }
Output: 2
Explanation: Considering b = 0: The value of the expression is abs(2 – (0 + 1)) + abs(2 – (0 + 2)) + abs(3 – (0 + 3)) + abs(5 – (0 + 4)) + abs(5 – (0 + 5)) = 1 + 0 + 0 + 1 + 0 = 2
Therefore, the minimum possible value for the expression is 2.

Input: arr[ ] = { 6, 5, 4, 3, 2, 1 }
Output: 18

Подход: учитывая, что B[i] = A[i] − i, задача состоит в том, чтобы свести к минимуму сумму abs (B[i] − b). Можно заметить, что лучше всего использовать b как медиану модифицированного массива B[]. Итак, после сортировки массива B[] проблему можно решить, выполнив шаги, указанные ниже .

• Пройдите по массиву arr[ ] и уменьшите каждый элемент по его индексу (i + 1) .
• Отсортируйте массив в порядке возрастания.
• Теперь выберите b как медиану arr[ ] , скажем, b = arr[N/2] .
• Инициализируйте переменную, скажем , как 0, чтобы сохранить минимально возможное значение выражения.
• Снова пройдитесь по массиву и обновите ans как abs(arr[i] – b).
• Возвращает значение ans .

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

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