Suma de array máxima posible después de realizar operaciones dadas

Dada la array arr[] de enteros positivos, un número entero Q y arrays X[] e Y[] de tamaño Q. Para cada elemento en las arrays X[] e Y[] , podemos realizar las siguientes operaciones:

• Para cada consulta de la array X[] e Y[], seleccione como máximo X[i] elementos de la array arr[] y reemplace todos los elementos seleccionados con el entero Y[i] .
• Después de realizar operaciones Q, la tarea es obtener la suma máxima de la array arr[] .

Ejemplos:

Entrada: arr[] = {5, 2, 6, 3, 8, 5, 4, 7, 9, 10}, Q = 3, X[] = {2, 4, 1}, Y[] = {4 , 3, 10} 
Salida: 68 
Explicación: 
Para i = 1, 
podemos reemplazar como máximo 2 elementos de la array arr[] con el número entero 4. Aquí, 2 elementos de la array arr[] son ​​más pequeños que 4, por lo que reemplazaremos los elementos 2 y 3 de la array arr[] con 4 y arr[] se convierte en {5, 4, 6, 4, 8, 5, 4, 7, 9, 10}.
Para i = 2, 
podemos reemplazar como máximo 4 elementos de la array ar[] con el número entero 3, pero ningún elemento de la array arr[] es menor que 3. Por lo tanto, no reemplazaremos nada.
Para i = 3, 
Podemos reemplazar como máximo 1 elemento de la array arr[] con el número entero 10, 9 elementos de la array arr[] son ​​más pequeños que 10. Para obtener la suma máxima, reemplazaremos el elemento más pequeño de la array arr[] con 10. Array arr [] después de la 3.ª operación = {5, 10, 6, 4, 8, 5, 10, 7, 9, 10}. La suma máxima posible es 68.
Entrada: ar[] = {200, 100, 200, 300}, Q = 2, X[] = {2, 3}, Y[] = {100, 90} Salida 
: 800 
Explicación : 
Para i = 1, 
podemos reemplazar como máximo 2 elementos de la array arr[] con el número entero 100, ningún elemento de la array arr[] es menor que 100. Por lo tanto, reemplazaremos 0 elementos.
Para i = 2, 
Podemos reemplazar como máximo 3 elementos de la array arr[] con el número entero 90, ningún elemento de la array arr[] es menor que 90. Entonces reemplazaremos 0 elementos. Entonces, la suma máxima que podemos obtener después de la operación q es 800.

Enfoque ingenuo: la idea ingenua es elegir elementos numéricos X[i] de la array arr[] . Si los elementos de la array son menores que Y[i] , actualice X[i] de dichos elementos. 
Complejidad de Tiempo: (N ² ) 
Espacio Auxiliar: O(1)
Enfoque Eficiente: La idea es usar una cola de prioridad para obtener el elemento con mayor valor antes que el elemento con menor valor, precisamente cola de prioridad de pares para almacenar valor con su frecuencia . A continuación se muestran los pasos:

• Inserte cada elemento de la array arr[] con su aparición en la cola de prioridad.
• Para cada elemento (digamos X[i] ) en la array X[], haga lo siguiente: 
  1. Elija como máximo X[i] número de elementos mínimos de la cola de prioridad.
  2. Reemplácelo con Y[i] si el elemento elegido es menor que Y[i].
  3. Vuelva a insertar el elemento reemplazado en la cola de prioridad con su frecuencia correspondiente.
• Después de las operaciones anteriores, la array arr[] tendrá elementos tales que la suma de todos los elementos sea máxima. Imprime la suma.

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

// C++ implementation to find the
// maximum possible sum of array
// after performing given operations
#include <bits/stdc++.h>
using namespace std;
 
// Function to get maximum
// sum after q operations
void max_sum(int ar[], int n,
             int q, int x[], int y[])
{
    int ans = 0, i;
 
    // priority queue to
    // get maximum sum
    priority_queue<pair<int, int> > pq;
 
    // Push pair, value and 1
    // in the priority queue
    for (i = 0; i < n; i++)
        pq.push({ ar[i], 1 });
 
    // Push pair, value (to be replaced)
    // and number of elements (to be replaced)
    for (i = 0; i < q; i++)
        pq.push({ y[i], x[i] });
 
    // Add top n elements from
    // the priority queue
    // to get max sum
    while (n > 0) {
 
        // pr is the pair
        // pr.first is the value and
        // pr.second is the occurrence
        auto pr = pq.top();
 
        // pop from the priority queue
        pq.pop();
 
        // Add value to answer
        ans += pr.first * min(n, pr.second);
 
        // Update n
        n -= pr.second;
    }
 
    cout << ans << "\n";
}
 
// Driver code
int main()
{
    int ar[] = { 200, 100, 200, 300 };
    int n = (sizeof ar) / (sizeof ar[0]);
    int q = 2;
    int x[] = { 2, 3 };
    int y[] = { 100, 90 };
    max_sum(ar, n, q, x, y);
 
    return 0;
}

// Java implementation to find the
// maximum possible sum of array
// after performing given operations
import java.util.*;
import java.lang.*;
 
class GFG{
 
static class pair
{
    int first, second;
    pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// Function to get maximum
// sum after q operations
static void max_sum(int ar[], int n, int q,
                    int x[], int y[])
{
    int ans = 0, i;
 
    // priority queue to
    // get maximum sum
    PriorityQueue<pair> pq = new PriorityQueue<>(
        (a, b) -> Integer.compare(a.second, b.second));
 
    // Push pair, value and 1
    // in the priority queue
    for(i = 0; i < n; i++)
        pq.add(new pair(ar[i], 1 ));
 
    // Push pair, value (to be replaced)
    // and number of elements (to be replaced)
    for(i = 0; i < q; i++)
        pq.add(new pair(y[i], x[i]));
 
    // Add top n elements from
    // the priority queue
    // to get max sum
    while (n > 0)
    {
         
        // pr is the pair
        // pr.first is the value and
        // pr.second is the occurrence
        pair pr = pq.peek();
 
        // pop from the priority queue
        pq.poll();
 
        // Add value to answer
        ans += pr.first * Math.min(n, pr.second);
 
        // Update n
        n -= pr.second;
    }
    System.out.println(ans);
}
 
// Driver Code
public static void main (String[] args)
{
    int ar[] = { 200, 100, 200, 300 };
    int n = ar.length;
    int q = 2;
    int x[] = { 2, 3 };
    int y[] = { 100, 90 };
     
    max_sum(ar, n, q, x, y);
}
}
 
// This code is contributed by offbeat

800

Complejidad de tiempo: O (N * log ₂ N), ya que estamos usando un bucle para atravesar N veces y la operación de cola de prioridad tomará log ₂ N veces.
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para la cola de prioridad.