Минимизируйте стоимость преобразования заданного массива от 1 до N с помощью заданных замен.

Даны два массива a[] и b[] длины N и целое число K (1 ≤ K ≤ N) . Все целые числа в массиве a[] лежат в диапазоне [1, K] . i -е значение в массиве b[] обозначает стоимость замены a[i] любым числом в диапазоне [1, N] . Задача состоит в том, чтобы найти минимальную стоимость замены элементов массива a[] для превращения его в перестановку от 1 до N .

Примечание. Перестановка от 1 до N содержит все значения от 1 до N в любом порядке, и ни одно значение не повторяется.

Примеры:

Input: K = 7, a[] = {1, 1, 3, 4, 5, 3, 7, 1}
b[] = {7, 5, 4, 8, 1, 3, 5, 2}
Output: 10
Explanation: In a[] some numbers are repeating which are 1, 1, 3, 3, 1.
Now, make two 1’s and one 3 unique.
Select a[1], a[5] and a[7] and replace them with 2, 6, and 8 to make array a permutation of 1 to 8.
The total cost is b[1] + b[5] + b[7] = 5 + 3 + 2 = 10.
This is the minimum cost to make a[] a permutation of 1 to 8.
Now, a[] becomes {1, 2, 3, 4, 5, 6, 7, 8}

Input: K = 3, a[] = {3, 1, 2}
b[] = {5, 3, 4}
Output: 0
Explanation: a[] is already a permutation of 1 to 3. So no need to replace any value.

Подход: Решение задачи основано на концепции хеширования . Сохраните элементы, которые повторяются, и замените все, кроме того, который имеет максимальную стоимость замены. Выполните шаги, указанные ниже, чтобы решить проблему:

• Инициализируйте карту для хранения a[i] и b[i] .
• Инициализируйте вектор, чтобы сохранить минимальный ответ.
• Теперь пройдитесь по обоим массивам.
  • Если a[i] отсутствует на карте, сохраните a[i] как ключ, а b[i] как значение на карте.
  • В противном случае, если a[i] присутствует, а значение a[i] , хранящееся в карте, меньше, чем b[i] , сохраните существующее значение a[i] в векторе v и измените значение в карте на b[ я] .
  • В противном случае сохраните b[i] в векторе v .
• Отсортируйте вектор v .
• Инициализируйте переменную ans = 0.
• Теперь пройдитесь по вектору (K — размер карты) раз и просуммируйте все значения вектора в ans .

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

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