Минимальная стоимость, чтобы сделать массив равным путем увеличения/уменьшения элементов

Учитывая массив, arr[] и массив стоимости cost[] , задача состоит в том, чтобы найти минимальную стоимость, чтобы сделать все элементы массива равными, увеличивая или уменьшая элемент по любому индексу на 1. Стоимость увеличения или уменьшения операция для элемента с индексом i — это стоимость [i].

Примеры:

Input: arr[] = {1, 3, 5, 2}, cost[] = {2, 3, 1, 14}
Output: 8
Explanation: On making all elements equal to 2 the cost is 1*2 + 1*3 + 3*1 = 8 which is the minimum cost.

Input: arr[] = {3, 3, 3, 3, 3}, cost[] = {1, 2, 3, 4, 5}
Output: 0
Explanation: All are same already in the array arr[].

Подход: Это можно решить, используя следующую идею.

The idea is to try converting each array to each of all values between [1, 10⁶] and convert all to that number that gives minimum cost. We use prefix sum and suffix sum technique to store the cost to convert all elements to that index i and finally take the minimum of  sum of prefix sum and suffix sum at index i.

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

• Инициализируйте переменную maxSize = 1000002 , в которой хранится максимальный размер.
• Инициализировать массив total_cost_at_i[] размера maxSize, в котором хранится общая стоимость аналогичного arr[i].
• Теперь пройдемся по массиву и добавим стоимость всех похожих элементов в массив total_cost_at_i[] .
• Возьмите переменную sum=0 , чтобы сохранить сумму стоимости до i.
• Объявите префикс двух массивов для хранения стоимости преобразования всех предыдущих элементов i-1 в i и суффикс для хранения стоимости преобразования всех элементов из i+1 в maxSize в i .
• Теперь возьмите минимум префикса [i] + суффикса [i] для каждого индекса и сохраните минимум в переменной min_cost.

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

Временная сложность: O(N), где N — размер массива.
Вспомогательное пространство: O(N)