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

Опубликовано: 21 Сентября, 2022

Для заданных двух массивов A[] и B[] , содержащих N целых чисел, задача состоит в том, чтобы найти минимальные операции, необходимые для того, чтобы сделать все элементы обоих массивов равными, где при каждой операции можно сделать следующее:

  • Уменьшите значение A[i] на 1 , где i находится в диапазоне [0, N) .
  • Уменьшите значение B[i] на 1 , где i находится в диапазоне [0, N) .
  • Уменьшите значение A[i] и B[i] на 1 , где i находится в диапазоне [0, N) .

Примечание. Элементы в массивах A[] и B[] не обязательно должны быть равны друг другу.

Пример:

Input: arr1[] = {1, 2, 3}, arr2[] = {5, 4, 3}
Output: 5
Explanation: Operations can be performed in the following way:

  1. Decrement element at index 2 of A[] by 1. Hence, A[] = {1, 2, 2}.
  2. Decrement element at index 2 of A[] by 1. Hence, A[] = {1, 2, 1}.
  3. Decrement element at index 0 of B[] by 1. Hence, B[] = {4, 4, 3}.
  4. Decrement element at index 0 of B[] by 1. Hence, B[] = {3, 4, 3}.
  5. Decrement element at index 1 of both A[] and B[] by 1. Hence A[] = {1, 1, 1} and B[] = {3, 3, 3}

Therefore, all the elements of both the arrays A[] and B[] can be made equal in 5 operation which is the minimum possible.

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

Подход: Данная проблема может быть решена с использованием жадного подхода. Поскольку все возможные операции только уменьшают значения массива, все элементы должны быть сделаны равными наименьшему элементу в данном массиве. Предположим , что min_A и min_B — наименьшие целые числа в массивах A[] и B[] соответственно. Следовательно, требуемый ответ будет суммой max(A[i] – min_A, B[i] – min_B) для всех возможных значений i в диапазоне [0, N) .

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

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ