Minimice el costo de hacer que el Array dado tenga una permutación de 1 a N mediante reemplazos dados

Dadas dos arrays a[] y b[] de longitud N y un entero K (1 ≤ K ≤ N) . Todos los enteros en la array a[] se encuentran dentro del rango [1, K] . i-ésimo valor en la array b[] denota el costo de reemplazar a[i] con cualquier número en el rango [1, N] . La tarea es encontrar el costo mínimo para reemplazar los elementos del arreglo a[] para convertirlo en una permutación de 1 a N.

Nota: Una permutación de 1 a N contiene todos los valores de 1 a N en cualquier orden y no se repite ningún valor.

Ejemplos:

Entrada: K = 7, a[] = {1, 1, 3, 4, 5, 3, 7, 1}
b[] = {7, 5, 4, 8, 1, 3, 5, 2}
Salida: 10
Explicación: En a[] se repiten algunos números que son 1, 1, 3, 3, 1.
Ahora, haz que dos 1 y un 3 sean únicos.
Seleccione a[1], a[5] y a[7] y reemplácelos con 2, 6 y 8 para hacer que la array sea una permutación de 1 a 8.
El costo total es b[1] + b[5] + b [7] = 5 + 3 + 2 = 10.
Este es el costo mínimo para hacer a[] una permutación de 1 a 8.
Ahora, a[] se convierte en {1, 2, 3, 4, 5, 6, 7, 8}

Entrada: K = 3, a[] = {3, 1, 2}
b[] = {5, 3, 4}
Salida: 0
Explicación: a[] ya es una permutación de 1 a 3. Por lo tanto, no es necesario reemplazar algún valor.

Planteamiento: La solución del problema se basa en el concepto de hashing . Almacene los elementos que se repiten y reemplace todos menos el que tenga el costo máximo de reemplazo. Siga los pasos que se mencionan a continuación para resolver el problema:

• Inicialice el mapa para almacenar a[i] y b[i] .
• Inicialice el vector para almacenar la respuesta mínima.
• Ahora atraviesa ambas arrays.
  • Si a[i] no está presente en el mapa, almacene a[i] como clave y b[i] como valor en el mapa.
  • De lo contrario, si a[i] está presente y el valor de a[i] almacenado en el mapa es menor que b[i] , almacene el valor existente de a[i] en un vector v y cambie el valor en el mapa a b[ yo] .
  • De lo contrario, almacene b[i] en el vector v .
• Ordenar el vector v .
• Inicialice la variable ans = 0.
• Ahora recorra el vector (K – tamaño del mapa) veces y sume todos los valores del vector en ans .

A continuación se muestra la implementación del enfoque anterior. 

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the minimum cost
int minCost(int a[], int b[], int N, int K)
{
    // Initialize map and vector
    map<int, int> m;
    vector<int> v;
 
    for (int i = 0; i < N; i++) {
        if (m[a[i]] == 0) {
            m[a[i]] = b[i];
        }
        else {
            if (m[a[i]] < b[i]) {
                v.push_back(m[a[i]]);
                m[a[i]] = b[i];
            }
            else {
                v.push_back(b[i]);
            }
        }
    }
    sort(v.begin(), v.end());
    int size = K - m.size();
    int ans = 0;
    for (int i = 0; i < size; i++) {
        ans += v[i];
    }
    return ans;
}
 
// Driver code
int main()
{
    int a[] = { 1, 1, 3, 1, 5, 3, 7, 1 };
    int b[] = { 5, 7, 4, 8, 1, 3, 5, 2 };
    int K = 7;
    int N = sizeof(a) / sizeof(a[0]);
     
    cout << minCost(a, b, N, K);
    return 0;
}

// JAVA code to implement the approach
import java.util.*;
class GFG
{
 
  // Function to calculate the minimum cost
  public static int minCost(int[] a, int[] b, int N,
                            int K)
  {
 
    // Initialize map and ArrayList
    HashMap<Integer, Integer> m
      = new HashMap<Integer, Integer>();
    ArrayList<Integer> v = new ArrayList<Integer>();
 
    for (int i = 0; i < N; i++) {
      if (m.containsKey(a[i])) {
        m.put(a[i], 0);
      }
    }
    for (int i = 0; i < N; i++) {
      if (m.get(a[i]) == null) {
        m.put(a[i], b[i]);
      }
      else {
        if (m.get(a[i]) < b[i]) {
          v.add(m.get(a[i]));
          m.put(a[i], b[i]);
        }
        else {
          v.add(b[i]);
        }
      }
    }
    Collections.sort(v);
    int size = K - m.size();
    int ans = 0;
    for (int i = 0; i < size; i++) {
      ans += v.get(i);
    }
    return ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int[] a = new int[] { 1, 1, 3, 1, 5, 3, 7, 1 };
    int[] b = new int[] { 5, 7, 4, 8, 1, 3, 5, 2 };
    int K = 7;
    int N = a.length;
 
    System.out.print(minCost(a, b, N, K));
  }
}
 
// This code is contributed by Taranpreet

// C# code to implement the approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to calculate the minimum cost
  static int minCost(int []a, int []b, int N, int K)
  {
 
    // Initialize map and vector
    Dictionary<int, int> m =
      new Dictionary<int, int>();
    ArrayList v = new ArrayList();
 
    for(int i = 0; i < N; i++) {
      if(!m.ContainsKey(a[i])) {
        m.Add(a[i], 0);
      }
    }
 
    for (int i = 0; i < N; i++) {
      if (m[a[i]] == 0) {
        m[a[i]] = b[i];
      }
      else {
        if (m[a[i]] < b[i]) {
          v.Add(m[a[i]]);
          m[a[i]] = b[i];
        }
        else {
          v.Add(b[i]);
        }
      }
    }
    v.Sort();
    int size = K - m.Count;
    int ans = 0;
    for (int i = 0; i < size; i++) {
      ans += (int)v[i];
    }
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int []a = { 1, 1, 3, 1, 5, 3, 7, 1 };
    int []b = { 5, 7, 4, 8, 1, 3, 5, 2 };
    int K = 7;
    int N = a.Length;
 
    Console.Write(minCost(a, b, N, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
      // JavaScript code for the above approach
 
      // Function to calculate the minimum cost
      function minCost(a, b, N, K) {
          // Initialize map and vector
          let m = new Map();
          let v = [];
 
          for (let i = 0; i < N; i++) {
              if (m.has(a[i]) == false) {
                  m.set(a[i], b[i]);
              }
              else {
                  if (m.get(a[i]) < b[i]) {
                      v.push(m.get(a[i]));
                      m.set(a[i], b[i]);
                  }
                  else {
                      v.push(b[i]);
                  }
              }
          }
          v.sort(function (a, b) { return a - b })
          let size = K - m.size;
          let ans = 0;
          for (let i = 0; i < size; i++) {
              ans += v[i];
          }
          return ans;
      }
 
      // Driver code
 
      let a = [1, 1, 3, 1, 5, 3, 7, 1];
      let b = [5, 7, 4, 8, 1, 3, 5, 2];
      let K = 7;
      let N = a.length;
 
      document.write(minCost(a, b, N, K));
 
     // This code is contributed by Potta Lokesh
  </script>

# Python code for the above approach
 
# Function to calculate the minimum cost
def minCost(a, b, N, K):
    # Initialize map and vector
    m = {}
    v = [];
 
    for  i in range(N):
        if (a[i] not in m):
            m[a[i]] = b[i]
         
        else:
            if (m[a[i]] < b[i]):
                v.append(m[a[i]]);
                m[a[i]] = b[i]
             
            else:
                v.append(b[i]);
 
    v.sort()
    size = K - len(m);
    ans = 0;
    for i in range(size):
        ans += v[i];
    return ans;
 
 
# Driver code
 
a = [1, 1, 3, 1, 5, 3, 7, 1];
b = [5, 7, 4, 8, 1, 3, 5, 2];
K = 7;
N = len(a)
 
print(minCost(a, b, N, K));
 
# This code is contributed by Saurabh Jaiswal

10

Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)