Maximice la suma de la array reemplazando como máximo los elementos L a R para las consultas Q

Dada una array arr[] que consta de N enteros y una array Query[][] que consta de M pares del tipo {L, R} , la tarea es encontrar la suma máxima de la array realizando las consultas Query[][ ] de modo que para cada consulta {L, R} reemplace como máximo L elementos de array por el valor R .

Ejemplos:

Entrada: arr[]= {5, 1, 4}, Consulta[][] = {{2, 3}, {1, 5}} Salida: 14 Explicación: Las siguientes son las operaciones realizadas:
Consulta 1
:
Para
la Consulta {2, 3}, no hagas nada.
Consulta 2: para la consulta {1, 5}, reemplace como máximo L(= 1) el elemento de array con el valor R(= 5), reemplace arr[1] con el valor 5. Después de los pasos anteriores, la array se modifica a {5
, 5, 4}. La suma de los elementos de la array es 14, que es el máximo.

Entrada: arr[] = {1, 2, 3, 4}, Consulta[][] = {{3, 1}, {2, 5}}
Salida: 17

Enfoque: el problema dado se puede resolver con la ayuda del enfoque codicioso . La idea principal para maximizar la suma de la array es realizar la consulta para aumentar el número mínimo a un valor máximo, ya que el orden de las operaciones no importa, ya que son independientes entre sí. Siga los pasos a continuación para resolver el problema dado:

• Mantenga una cola de prioridad de montón mínimo y almacene todos los elementos de la array.
• Recorra la array dada de consultas Q[][] y para cada consulta {L, R} realice los siguientes pasos:
  • Cambie el valor de como máximo L elementos menores que R al valor R , comenzando desde el más pequeño.
  • Realice la operación anterior, extraiga los elementos más pequeños que R y presione R en sus lugares en la cola de prioridad .
• Después de completar los pasos anteriores, imprima la suma de los valores almacenados en la cola de prioridad como la suma máxima.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum array
// sum after performing M queries
void maximumArraySumWithMQuery(
    int arr[], vector<vector<int> >& Q,
    int N, int M)
{
 
    // Maintain a min-heap Priority-Queue
    priority_queue<int, vector<int>,
                   greater<int> >
        pq;
 
    // Push all the elements in the
    // priority queue
    for (int i = 0; i < N; i++) {
        pq.push(arr[i]);
    }
 
    // Iterate through M Operations
    for (int i = 0; i < M; i++) {
 
        // Iterate through the total
        // possible changes allowed
        // and maximize the array sum
        int l = Q[i][0];
        int r = Q[i][1];
 
        for (int j = 0; j < l; j++) {
 
            // Change the value of elements
            // less than r to r, starting
            // from the smallest
            if (pq.top() < r) {
                pq.pop();
                pq.push(r);
            }
 
            // Break if current element >= R
            else {
                break;
            }
        }
    }
 
    // Find the resultant maximum sum
    int ans = 0;
 
    while (!pq.empty()) {
        ans += pq.top();
        pq.pop();
    }
 
    // Print the sum
    cout << ans;
}
 
// Driver Code
int main()
{
    int N = 3, M = 2;
    int arr[] = { 5, 1, 4 };
    vector<vector<int> > Query
        = { { 2, 3 }, { 1, 5 } };
 
    maximumArraySumWithMQuery(
        arr, Query, N, M);
 
    return 0;
}

// Java program for the above approach
 
import java.util.PriorityQueue;
 
class GFG {
 
    // Function to find the maximum array
    // sum after performing M queries
    public static void maximumArraySumWithMQuery(int arr[], int[][] Q, int N, int M) {
 
        // Maintain a min-heap Priority-Queue
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
 
        // Push all the elements in the
        // priority queue
        for (int i = 0; i < N; i++) {
            pq.add(arr[i]);
        }
 
        // Iterate through M Operations
        for (int i = 0; i < M; i++) {
 
            // Iterate through the total
            // possible changes allowed
            // and maximize the array sum
            int l = Q[i][0];
            int r = Q[i][1];
 
            for (int j = 0; j < l; j++) {
 
                // Change the value of elements
                // less than r to r, starting
                // from the smallest
                if (pq.peek() < r) {
                    pq.remove();
                    pq.add(r);
                }
 
                // Break if current element >= R
                else {
                    break;
                }
            }
        }
 
        // Find the resultant maximum sum
        int ans = 0;
 
        while (!pq.isEmpty()) {
            ans += pq.peek();
            pq.remove();
        }
 
        // Print the sum
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String args[]) {
        int N = 3, M = 2;
        int arr[] = { 5, 1, 4 };
        int[][] Query = { { 2, 3 }, { 1, 5 } };
 
        maximumArraySumWithMQuery(arr, Query, N, M);
 
    }
}
 
// This code is contributed by saurabh_jaiswal.

# Python program for the above approach
from queue import PriorityQueue
 
# Function to find the maximum array
# sum after performing M queries
def maximumArraySumWithMQuery(arr, Q, N, M):
 
    # Maintain a min-heap Priority-Queue
    pq = PriorityQueue()
 
    # Push all the elements in the
    # priority queue
    for i in range(N):
        pq.put(arr[i])
 
    # Iterate through M Operations
    for i in range(M):
 
        # Iterate through the total
        # possible changes allowed
        # and maximize the array sum
        l = Q[i][0];
        r = Q[i][1];
 
        for j in range(l):
 
            # Change the value of elements
            # less than r to r, starting
            # from the smallest
            if (pq.queue[0] < r):
                pq.get();
                pq.put(r);
 
            # Break if current element >= R
            else:
                break
         
    # Find the resultant maximum sum
    ans = 0;
     
    while ( not pq.empty() ):
        ans += pq.queue[0];
        pq.get();
 
    # Print the sum
    print(ans)
 
# Driver Code
N = 3
M = 2
arr = [5, 1, 4]
Query = [[2, 3], [1, 5]]
 
maximumArraySumWithMQuery(arr, Query, N, M)
 
# This code is contributed by gfgking.

14

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