Минимальная стоимость для обеспечения четности элементов путем удаления подмассива

Учитывая arr[] длины N , задача состоит в том, чтобы сделать четность arr[] одинаковой с помощью приведенной ниже операции:

• Выберите подмассив, содержащий элементы одинаковой четности.
• Удалить подмассив.
• Стоимость удаления этого подмассива равна (абсолютная смежная разность всех элементов, присутствующих в подмассиве)*(длина подмассива) . За а подмассив длины 1, стоимость будет элементом, присутствующим в этом подмассиве.

Примеры:

Input: N = 3, arr[] = {2, 4, 6}
Output: 0
Explanation: All the elements of given arr[] are even, Input arr[] has even parity already. Therefore, minimum cost is 0

Input: N = 4, arr[] = {22, 42, 64, 7}
Output: 7
Explanation: It will be optimal to remove sub-array {A_4, .  . .  , A₄} = {7}. Length of Sub-array is one, Therefore, minimum cost to remove this sub-array is = 7. After removing {7}, arr[] = {22, 42, 64}. it can be verified that now arr[] contains only even elements. Therefore, minimum cost to make parity of arr[] is 7.

Input: N = 7, arr[] = {2, 3, 1, 5, 4, 6, 4} 
Output: 14
Explanation: It will be optimal to make arr[] of odd parity.
First sub-array = {2}, Cost = 2
Second sub-array = {4, 6, 4}, cost = ( |6-4|+|4-6| )*(3) = (2+2)*(3) = 12
Hence, Total minimum cost will be 2+12=14. arr[] after removing both sub-arrays = {3, 1, 5} 

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

The problem is based on Greedy approach for finding minimum cost. Find all the sub-arrays of even and odd parity, Then calculate minimum cost for both in two different variables. Print the minimum between both costs.

Следуйте иллюстрации ниже для лучшего понимания:

Иллюстрировано:

Conosider array arr[] = {2, 3, 1, 5, 4, 6, 4}

Let us make the parity of given arr[] odd and even one by one.

• Even parity arr[]: For making arr[] of even parity, We have to remove all sub-arrays having odd parity along with their cost. There is only one odd subarray present in arr[] from index 1 to 3.
  • First odd  sub-array = {3, 1, 5}. Cost for removing this sub-array = ( |1-3|+|5-1| )*(3) = 6*3=18
  • arr[] after removing the subarray is {2, 4, 6, 4}. It can be verified that now arr[] have even parity having costs as 18.
• Odd parity arr[]: For making arr[] of odd parity, We have to remove all sub-arrays having even parity along with their cost. There are two even subarrays present in arr[] from index 0 to 0 and 4 to 6 respectively.
  • First even sub-array = {2}. Cost for removing this sub-array = 2
  • Second even sub-array = {4, 6, 4}. Cost for removing this sub-array = ( |6-4|+|4-6| )*(3) = 4*3 = 12 
  • arr[] after removing sub-arrays {1} and {4, 6, 4} is {1, 3, 5}. It can be verified that now arr[] have odd parity having costs as 2+12=14.

Now, We have test arr[] for both parities. The minimum cost will be min(cost for making arr[] parity even, cost for making arr[] parity odd).

Minimum cost = min(14, 18) = 14.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Рассмотрим две переменные (скажем, min_cost_even и min_cost_odd ). для удержания минимальной стоимости сделать четность arr[] нечетной или четной соответственно.
• Находить все подмассивы имеют нечетную четность. Рассчитайте стоимость каждого подмассива и добавьте ее в min_cost_even .
• Найти все подмассивы, имеющие четную четность, Рассчитать стоимость каждого подмассива и добавьте его в min_cost_odd .
• Возвращает минимальное значение между обеими затратами, полученными на шагах 2 и 3, т. е . min(min_cost_odd, min_cost_even).

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

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

Статьи по Теме:

• Введение в массивы — учебные пособия по структуре данных и алгоритмам
• Введение в жадный алгоритм — учебные пособия по структурам данных и алгоритмам