Максимизируйте сумму измененных значений после перестановки данного массива на основе массива условий

Имея двоичный массив arr1[] и массив целых чисел arr2[] , каждый из которых имеет длину N , задача состоит в том, чтобы переупорядочить элементы в массиве arr2 так, чтобы общая стоимость была максимальной. Общая сгенерированная стоимость рассчитывается путем суммирования измененных значений в массиве arr2 . Значения изменяются таким образом, что целое число, соответствующее значению 0 в массиве arr1 , не влияет на другие элементы, но целое число, соответствующее значению 1 в массиве arr1 , может удвоить значение следующего целого числа.

Примеры:

Input: N = 2, arr1 = [1, 0], arr2 = [3, 4]
Output: 11
Explanation: Element 3 corresponds to value 1 so it can double the value of the next element. Out of 2 arrangements possible [3, 4] and [4, 3] so in the 1st case cost generated is 3+4*2 = 11 and in the 2nd case the cost generated is 4+3=7 

Input: N = 5, arr1 = [1, 0, 1, 0, 1], arr2 = [3, 7, 2, 12, 5]
Output: 53
Explanation: Maximum cost can be generated in the arrangement [3, 7, 2, 5, 12] here 1st, 3rd and 4th elements correspond to value 1 and hence their next elements cost can be doubled so cost is 3+7*2+2+5*2+12*2=53

Подход: Данная проблема может быть решена с использованием жадного подхода. Идея состоит в том, чтобы отсортировать массив в порядке убывания, а затем повторить его, чтобы вычислить сгенерированную стоимость. Можно выполнить следующие шаги:

• Инициализируем вспомогательный массив arr1 и скопируем в него все элементы массива arr2 , которым соответствует значение 1 в массиве arr1
• Найдите минимальное значение в массиве arr1, удалите его из массива и сохранить в переменной, скажем, val
• Отсортировать массив arr2 по убыванию
• Инициализировать переменную и рассчитать максимальную сгенерированную стоимость
• Если все элементы в массиве arr1 равны 1, удвойте значение всех элементов, кроме минимального значения val , и верните их сумму.
• В противном случае добавьте двойное значение элементов arr1 в ans и оставит все элементы без изменений.

Временная сложность: O (N * log N)
Космическая сложность: O(N)