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

Учитывая массив arr[] размера N и два целых числа X и Y , задача состоит в том, чтобы найти минимальную стоимость, необходимую для изменения массива, чтобы даже индексы имели четные элементы и нечетные индексы содержат нечетные элементы либо путем замены двух элементов массива со стоимостью X , либо путем увеличения или уменьшения на 1 элемента со стоимостью Y .

Примеры:

Input: arr[] = {5, 3, 7, 2, 1}, X = 1, Y = 2
Output: 5
Explanation:
Following are the operations performed:
Operation 1: Swap the array elements at indices 0 and 3, modifies the array to {2, 3, 7, 5, 1}. The cost of this operations is X(= 1).
Operation 2: Incrementing the array elements at index 2, modifies the array to {2, 3, 8, 5, 1}. The cost of this operations is Y(= 2).
Operation 3: Incrementing the array elements at index 4, modifies the array to {2, 3, 8, 5, 2}. The cost of this operations is Y(= 2).
Therefore, the total cost is 1 + 2 + 2 = 5, which is minimum.
 

Input: arr[] = {1, 2, 3, 4}, X = 1, Y = 2
Output: 2

Подход: Данную проблему можно решить, используя следующие наблюдения, сначала найдя количество элементов, которые неправильно размещены в нечетных и четных индексах как oddCount и evenCount соответственно:

• Случай 1: стоимость может быть рассчитана путем выполнения операций обмена минимума изodCount и evenCount по стоимости X и выполнения операции уменьшения на оставшиеся элементы по стоимости Y .
• Случай 2: стоимость может быть рассчитана путем выполнения операции уменьшения на оставшиеся элементы по стоимости Y .

Минимум затрат, полученный в двух вышеперечисленных случаях, является искомым результатом.

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

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