Dadas dos arrays arr[] que contienen N enteros y Q[][] que contienen K consultas donde cada consulta representa un rango [L, R] . La tarea es reorganizar el arreglo y encontrar la máxima suma posible de todos los subarreglos donde cada subarreglo está definido por los elementos del arreglo en el rango [L, R] dado por cada consulta.
Nota: la indexación basada en 1 se usa en la array Q[][] para indicar los rangos.
Ejemplos:
Entrada: arr[] = { 2, 6, 10, 1, 5, 6 }, Q[][2] = {{1, 3}, {4, 6}, {3, 4}}
Salida: 46
Explicación :
Una forma posible es reorganizar la array a arr[] = {2, 6, 10, 6, 5, 1}.
En este arreglo:
La suma del subarreglo en el rango [1, 3] = 2 + 6 + 10 = 18.
La suma del subarreglo en el rango [4, 6] = 6 + 5 + 1 = 12.
La suma del subarreglo en el rango [3, 4] = 10 + 6 = 16.
La suma total de todos los subarreglos = 46 que es el máximo posible.
Entrada: arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 }, Q[][2] = {{1, 4}, {5, 5}, {7, 8}, {8, 8}}
Salida: 43
Explicación:
una forma posible es reorganizar la array a arr[] = {2, 3, 4, 5, 6, 1, 7, 8}.
En este arreglo:
La suma del subarreglo en el rango [1, 4] = 2 + 3 + 4 + 5 = 14.
La suma del subarreglo en el rango [5, 5] = 6 = 6.
La suma del subarreglo en el rango [7, 8] = 7 + 8 = 15.
La suma del subarreglo en el rango [8, 8] = 8 = 8.
La suma total de todos los subarreglos = 43 que es el máximo posible.
Enfoque: al observar claramente, una conclusión que se puede sacar es que obtenemos la suma máxima cuando los elementos máximos se incluyen en tantos subarreglos como sea posible. Para esto, necesitamos encontrar la cantidad de veces que se incluye cada índice iterando todas las consultas.
Por ejemplo: Sea la array arr[] = {2, 6, 10, 6, 5, 1} y las consultas sean Q[][] = {{1, 3}, {4, 6}, {3, 4}} .
- Paso 1: Cree una array de conteo C[] de tamaño N. Entonces, inicialmente, la array de conteo C[] = {0, 0, 0, 0, 0, 0} .
- Paso 2: Para la consulta [1, 3] , los elementos en el índice [1, 3] se incrementan en 1. La array de conteo después de esta consulta se convierte en {1, 1, 1, 0, 0, 0} .
- Paso 3: De manera similar, para la siguiente consulta, la array de conteo se convierte en {1, 1, 1, 1, 1, 1} y finalmente, después de la tercera consulta, la array de conteo se convierte en {1, 1, 2, 2, 1, 1} .
- Paso 4: Después de obtener la array de conteo, la idea es usar la clasificación para obtener la suma máxima.
- Paso 5: Después de ordenar, la array C[] = {1, 1, 1, 1, 2, 2} y arr[] = {1, 2, 5, 6, 6, 10} . La suma máxima posible es la suma ponderada de ambas arrays , es decir:
suma = ((1 * 1) + (1 * 2) + (1 * 5) + (1 * 6) + (2 * 6) + (2 * 10)) = 46
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the maximum sum
// after rearranging the array for K queries
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum sum after
// rearranging array elements
int maxSumArrangement(int A[], int R[][2],
int N, int M)
{
// Auxiliary array to find the
// count of each selected elements
int count[N];
// Initialize with 0
memset(count, 0, sizeof count);
// Finding count of every element
// to be selected
for (int i = 0; i < M; ++i) {
int l = R[i][0], r = R[i][1] + 1;
// Making it to 0-indexing
l--;
r--;
// Prefix sum array concept is used
// to obtain the count array
count[l]++;
if (r < N)
count[r]--;
}
// Iterating over the count array
// to get the final array
for (int i = 1; i < N; ++i) {
count[i] += count[i - 1];
}
for (int i = 0; i < N; ++i) {
cout<<count[i];
}
// Variable to store the maximum sum
int ans = 0;
// Sorting both the arrays
sort(count, count + N);
sort(A, A + N);
for (int i = 0; i < N; ++i) {
cout<<endl<<A[i];
}
// Loop to find the maximum sum
for (int i = N - 1; i >= 0; --i) {
ans += A[i] * count[i];
}
return ans;
}
// Driver code
int main()
{
int A[] = { 2, 6, 10, 1, 5, 6 };
int R[][2]
= { { 1, 3 }, { 4, 6 }, { 3, 4 } };
int N = sizeof(A) / sizeof(A[0]);
int M = sizeof(R) / sizeof(R[0]);
cout << maxSumArrangement(A, R, N, M);
return 0;
}
Java
// Java program to find the maximum sum
// after rearranging the array for K queries
import java.util.*;
class GFG
{
// Function to find maximum sum after
// rearranging array elements
static int maxSumArrangement(int A[], int R[][],
int N, int M)
{
// Auxiliary array to find the
// count of each selected elements
int count[] = new int[N];
int i;
// Finding count of every element
// to be selected
for ( i = 0; i < M; ++i) {
int l = R[i][0], r = R[i][1] + 1;
// Making it to 0-indexing
l--;
r--;
// Prefix sum array concept is used
// to obtain the count array
count[l]++;
if (r < N)
count[r]--;
}
// Iterating over the count array
// to get the final array
for (i = 1; i < N; ++i) {
count[i] += count[i - 1];
}
// Variable to store the maximum sum
int ans = 0;
// Sorting both the arrays
Arrays.sort( count);
Arrays.sort(A);
// Loop to find the maximum sum
for (i = N - 1; i >= 0; --i) {
ans += A[i] * count[i];
}
return ans;
}
// Driver code
public static void main(String []args)
{
int A[] = { 2, 6, 10, 1, 5, 6 };
int R[][]
= { { 1, 3 }, { 4, 6 }, { 3, 4 } };
int N = A.length;
int M = R.length;
System.out.print(maxSumArrangement(A, R, N, M));
}
}
// This code is contributed by chitranayal
Python3
# Python3 program to find the maximum sum # after rearranging the array for K queries # Function to find maximum sum after # rearranging array elements def maxSumArrangement( A, R, N, M): # Auxiliary array to find the # count of each selected elements # Initialize with 0 count = [0 for i in range(N)] # Finding count of every element # to be selected for i in range(M): l = R[i][0] r = R[i][1] + 1 # Making it to 0-indexing l = l - 1 r = r - 1 # Prefix sum array concept is used # to obtain the count array count[l] = count[l] + 1 if (r < N): count[r] = count[r] - 1 # Iterating over the count array # to get the final array for i in range(1, N): count[i] = count[i] + count[i - 1] # Variable to store the maximum sum ans = 0 # Sorting both the arrays count.sort() A.sort() # Loop to find the maximum sum for i in range(N - 1, -1, -1): ans = ans + A[i] * count[i] return ans # Driver code A = [ 2, 6, 10, 1, 5, 6 ] R = [ [ 1, 3 ], [ 4, 6 ], [ 3, 4 ] ] N = len(A) M = len(R) print(maxSumArrangement(A, R, N, M)) # This code is contributed by Sanjit_Prasad
C#
// C# program to find the maximum sum
// after rearranging the array for K queries
using System;
class GFG
{
// Function to find maximum sum after
// rearranging array elements
static int maxSumArrangement(int []A, int [,]R,
int N, int M)
{
// Auxiliary array to find the
// count of each selected elements
int []count = new int[N];
int i;
// Finding count of every element
// to be selected
for ( i = 0; i < M; ++i) {
int l = R[i, 0], r = R[i, 1] + 1;
// Making it to 0-indexing
l--;
r--;
// Prefix sum array concept is used
// to obtain the count array
count[l]++;
if (r < N)
count[r]--;
}
// Iterating over the count array
// to get the readonly array
for (i = 1; i < N; ++i) {
count[i] += count[i - 1];
}
// Variable to store the maximum sum
int ans = 0;
// Sorting both the arrays
Array.Sort( count);
Array.Sort(A);
// Loop to find the maximum sum
for (i = N - 1; i >= 0; --i) {
ans += A[i] * count[i];
}
return ans;
}
// Driver code
public static void Main(String []args)
{
int []A = { 2, 6, 10, 1, 5, 6 };
int [,]R
= { { 1, 3 }, { 4, 6 }, { 3, 4 } };
int N = A.Length;
int M = R.GetLength(0);
Console.Write(maxSumArrangement(A, R, N, M));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
//Javascript program to find the maximum sum
// after rearranging the array for K queries
//function to sort a array
function arrSort(a, n) {
var i, j, min, temp;
for (i = 0; i < n - 1; i++) {
min = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[min])
min = j;
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
// Function to find maximum sum after
// rearranging array elements
function maxSumArrangement(A, R, N, M)
{
// Auxiliary array to find the
// count of each selected elements
var count = new Array(N);
// Initialize with 0
count.fill(0);
// Finding count of every element
// to be selected
for (var i = 0; i < M; i++) {
var l = R[i][0], r = R[i][1] + 1;
// Making it to 0-indexing
l--;
r--;
// Prefix sum array concept is used
// to obtain the count array
count[l]++;
if (r < N)
count[r]--;
}
// Iterating over the count array
// to get the final array
for (var i = 1; i < N; ++i) {
count[i] += count[i - 1];
}
// Variable to store the maximum sum
var ans = 0;
// Sorting both the arrays
count.sort();
arrSort(A,N);
// Loop to find the maximum sum
for (var i = N - 1; i >= 0; --i) {
ans += A[i] * count[i];
}
return ans;
}
var A = [ 2, 6, 10, 1, 5, 6 ];
var R = [ [ 1, 3 ], [ 4, 6 ], [ 3, 4 ] ];
var N = A.length;
var M = R.length;
document.write( maxSumArrangement(A, R, N, M));
//This code is contributed by SoumikMondal
</script>
46
Complejidad de tiempo: O(N* log(N))
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA