Dada una array arr[] de N enteros y un entero K . También se dan consultas Q que tienen dos números L y R . Para cada consulta, puede aumentar todos los elementos de la array en el rango de índice [L, R] en 1 . La tarea es elegir exactamente K consultas de Q consultas de modo que la suma de la array al final se maximice. Imprime la suma después de realizar K tales consultas.
Ejemplos:
Entrada: arr[] = {1, 1, 2, 2, 2, 3},
que[] = {{0, 4}, {1, 2}, {2, 5}, {2, 3}, { 2, 4}},
K = 3
Salida: 23
Elegimos la primera, tercera y quinta consulta.
Después de realizar la primera consulta -> arr[] = {2, 2, 3, 3, 3, 3}
Después de realizar la tercera consulta -> arr[] = {2, 2, 4, 4, 4, 4}
Después de realizar la quinta consulta -> arr[] = {2, 2, 5, 5, 5, 4}
Y la suma de la array es 2 + 2 + 5 + 5 + 5 + 4 = 23.Entrada: arr[] = {4, 5, 4, 21, 22},
que[] = {{1, 2}, {2, 2}, {2, 4}, {2, 2}},
K = 2
Salida: 61
Enfoque ingenuo: un enfoque ingenuo es usar programación dinámica y combinatoria, en el que elegimos cualquier consulta K de Q. La combinación que dé la suma máxima de la array será la respuesta.
Complejidad de tiempo : O(N*N*K), ya que usaremos recursividad con memorización.
Espacio auxiliar: O(N*N*K), ya que usaremos espacio extra para la memorización.
Enfoque eficiente: ya que necesitamos maximizar la suma de la array al final. Solo tenemos que elegir aquellas consultas que afecten al número máximo de elementos de la array, es decir, con rangos más grandes. Cada consulta contribuye (R – L + 1) al aumento de la suma si se elige. La suma de los elementos de la array después de realizar dichas consultas será (suma inicial de la array + (Contribución de K consultas)) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to perform K queries out
// of Q to maximize the final sum
int getFinalSum(int a[], int n, pair<int, int> queries[],
int q, int k)
{
int answer = 0;
// Get the initial sum
// of the array
for (int i = 0; i < n; i++)
answer += a[i];
vector<int> contribution;
// Stores the contribution of every query
for (int i = 0; i < q; i++) {
contribution.push_back(queries[i].second
- queries[i].first + 1);
}
// Sort the contribution of queries
// in descending order
sort(contribution.begin(), contribution.end(),
greater<int>());
int i = 0;
// Get the K most contributions
while (i < k) {
answer += contribution[i];
i++;
}
return answer;
}
// Driver code
int main()
{
int a[] = { 1, 1, 2, 2, 2, 3 };
int n = sizeof(a) / sizeof(a[0]);
pair<int, int> queries[] = { { 0, 4 },
{ 1, 2 },
{ 2, 5 },
{ 2, 3 },
{ 2, 4 } };
int q = sizeof(queries) / sizeof(queries[0]);
int k = 3;
cout << getFinalSum(a, n, queries, q, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
//pair class
static class pair
{
int first,second;
pair(int f,int s)
{
first = f;
second = s;
}
}
// Function to perform K queries out
// of Q to maximize the final sum
static int getFinalSum(int a[], int n, pair queries[],
int q, int k)
{
int answer = 0;
// Get the initial sum
// of the array
for (int i = 0; i < n; i++)
answer += a[i];
Vector<Integer> contribution = new Vector<Integer>();
// Stores the contribution of every query
for (int i = 0; i < q; i++)
{
contribution.add(queries[i].second
- queries[i].first + 1);
}
//comparator
Comparator<Integer> Comp = new Comparator<Integer>()
{
public int compare(Integer e1,Integer e2)
{
if(e1 > e2)
return -1;
else
return 1;
}
};
// Sort the contribution of queries
// in descending order
Collections.sort(contribution,Comp);
int i = 0;
// Get the K most contributions
while (i < k)
{
answer += (int) contribution.get(i);
i++;
}
return answer;
}
// Driver code
public static void main(String args[])
{
int a[] = { 1, 1, 2, 2, 2, 3 };
int n = a.length;
pair queries[] = new pair[5];
queries[0] = new pair( 0, 4 );
queries[1] = new pair( 1, 2 );
queries[2] = new pair( 2, 5 );
queries[3] = new pair( 2, 3 );
queries[4] = new pair( 2, 4 );
int q = queries.length;
int k = 3;
System.out.println( getFinalSum(a, n, queries, q, k));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python 3 implementation of the approach # Function to perform K queries out # of Q to maximize the final sum def getFinalSum(a, n, queries, q, k): answer = 0 # Get the initial sum # of the array for i in range(n): answer += a[i] contribution = [] # Stores the contribution of every query for i in range(q): contribution.append(queries[i][1]- queries[i][0] + 1) # Sort the contribution of queries # in descending order contribution.sort(reverse = True) i = 0 # Get the K most contributions while (i < k): answer += contribution[i] i += 1 return answer # Driver code if __name__ == '__main__': a = [1, 1, 2, 2, 2, 3] n = len(a) queries = [[0, 4], [1, 2], [2, 5], [2, 3], [2, 4]] q = len(queries); k = 3 print(getFinalSum(a, n, queries, q, k)) # This code is contributed by # Surendra_Gangwar
Javascript
<script>
// JavaScript implementation of the approach
// Function to perform K queries out
// of Q to maximize the final sum
const getFinalSum = (a, n, queries, q, k) => {
let answer = 0;
// Get the initial sum
// of the array
for (let i = 0; i < n; i++)
answer += a[i];
let contribution = [];
// Stores the contribution of every query
for (let i = 0; i < q; i++) {
contribution.push(queries[i][1] - queries[i][0] + 1);
}
// Sort the contribution of queries
// in descending order
contribution.sort((a, b) => b - a);
let i = 0;
// Get the K most contributions
while (i < k) {
answer += contribution[i];
i++;
}
return answer;
}
// Driver code
const a = [1, 1, 2, 2, 2, 3];
const n = a.length;
const queries = [
[0, 4],
[1, 2],
[2, 5],
[2, 3],
[2, 4]
];
const q = queries.length;
let k = 3;
document.write(getFinalSum(a, n, queries, q, k));
// This code is contributed by rakeshsahni
</script>
23
Complejidad de tiempo: O(max(n,k,q*log(q))), ya que estamos usando un ciclo para atravesar n y k veces y estamos usando una función de ordenación para ordenar una array de tamaño q.
Espacio auxiliar: O(q), ya que estamos usando espacio adicional para la contribución de la array.