Minimizar la Suma de todos los subarreglos formados por los productos de los mismos elementos indexados

Dados dos arreglos arr[] y arr2[] de longitud N , la tarea es encontrar la suma mínima de todos los subarreglos formados por los productos de los mismos elementos indexados de ambos arreglos después de reorganizar el segundo arreglo.

Nota: Dado que la respuesta puede ser muy grande, imprima la respuesta módulo 10 9 + 7 .

Ejemplos:

Entrada: arr[] = {1, 2}, arr2[] = {2, 3} 
Salida: 14 
Explicación: 
Reorganizar arr2[] a {3, 2} 
Por lo tanto, el producto de los mismos elementos indexados de dos arrays se convierte en { 3, 4}. 
Los subarreglos posibles son {3}, {4}, {3, 4} 
Suma de los subarreglos = 3 + 4 + 7 = 14.
Entrada: arr[] = {1, 2, 3}, arr2[] = {2, 3, 2} 
Salida: 43 
Explicación: 
Reorganizar arr2[] a {3, 2, 2} 
Por lo tanto, el producto de los mismos elementos indexados de dos arrays se convierte en {3, 4, 6}. 
Por lo tanto, suma de todos los subarreglos = 3 + 4 + 6 + 7 + 10 + 13 = 43

Enfoque: 
Se puede observar que, i -ésimo elemento ocurre en (i + 1)*(n – i) subarreglos. Por lo tanto, la tarea es maximizar la suma de (i + 1)*(n – i)* a[i] * b[i] . Siga los pasos a continuación para resolver el problema: 
 

  • Dado que los elementos de arr2[] solo se pueden reorganizar, el valor de (i + 1)*(n – i) * a[i] es constante para cada i -ésimo elemento.
  • Por lo tanto, calcule el valor de (i + 1)*(n – i)* a[i] para todos los índices y luego ordene los productos.
  • Ordene la array arr2[] en orden descendente .
  • Para cada i -ésimo índice, calcule la suma del producto de los valores de (i + 1)*(n – i)* a[i] en orden descendente y arr2[i] en orden ascendente.

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
const int mod = (int)1e9 + 7;
 
// Returns the greater of
// the two values
bool comp(ll a, ll b)
{
    if (a > b)
        return true;
    else
        return false;
}
 
// Function to rearrange the second array such
// that the sum of its product of same indexed
// elements from both the arrays is minimized
ll findMinValue(vector<ll>& a, vector<ll>& b)
{
 
    int n = a.size();
 
    // Stores (i - 1) * (n - i) * a[i]
    // for every i-th element
    vector<ll> pro(n);
 
    for (int i = 0; i < n; ++i) {
 
        // Updating the value of pro
        // according to the function
        pro[i] = ((ll)(i + 1) * (ll)(n - i));
        pro[i] *= (1LL * a[i]);
        ;
    }
 
    // Sort the array in reverse order
    sort(b.begin(), b.end(), comp);
 
    // Sort the products
    sort(pro.begin(), pro.end());
 
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
 
        // Updating the ans
        ans += (pro[i] % mod * b[i]) % mod;
        ans %= mod;
    }
 
    // Return the ans
    return ans;
}
 
// Driver code
int main()
{
 
    vector<ll> a = { 1, 2, 3 };
    vector<ll> b = { 2, 3, 2 };
    // Function call
    cout << findMinValue(a, b) << endl;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
static int mod = (int)1e9 + 7;
 
// Function to rearrange the second array such
// that the sum of its product of same indexed
// elements from both the arrays is minimized
static int findMinValue(int [] a, int []b)
{
    int n = a.length;
 
    // Stores (i - 1) * (n - i) * a[i]
    // for every i-th element
    int [] pro = new int[n];
 
    for(int i = 0; i < n; ++i)
    {
         
        // Updating the value of pro
        // according to the function
        pro[i] = ((i + 1) * (n - i));
        pro[i] *= (1L * a[i]);
        ;
    }
 
    // Sort the array in reverse order
    Integer[] input = Arrays.stream(b).boxed(
                      ).toArray(Integer[]::new);
                       
    Arrays.sort(input, (x, y) -> y - x);
    b = Arrays.stream(input).mapToInt(
        Integer::intValue).toArray();
         
    // Sort the products
    Arrays.sort(pro);
 
    int ans = 0;
    for(int i = 0; i < n; ++i)
    {
         
        // Updating the ans
        ans += (pro[i] % mod * b[i]) % mod;
        ans %= mod;
    }
 
    // Return the ans
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int []a = { 1, 2, 3 };
    int []b = { 2, 3, 2 };
     
    // Function call
    System.out.print(findMinValue(a, b) + "\n");
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 Program to implement
# the above approach
mod = 1e9 +7
 
# Function to rearrange
# the second array such
# that the sum of its
# product of same indexed
# elements from both
# the arrays is minimized
def findMinValue(a, b):
 
    n = len(a)
 
    # Stores (i - 1) * (n - i) * a[i]
    # for every i-th element
    pro = [0] * (n)
 
    for i in range (n):
 
        # Updating the value of pro
        # according to the function
        pro[i] = ((i + 1) * (n - i))
        pro[i] *= (a[i])
 
    # Sort the array in reverse order
    b.sort(reverse = True)
 
    # Sort the products
    pro.sort()
 
    ans = 0
    for i in range (n):
 
        # Updating the ans
        ans += (pro[i] % mod * b[i]) % mod
        ans %= mod
    
    # Return the ans
    return ans
 
# Driver code
if __name__ == "__main__":
 
    a = [1, 2, 3]
    b = [2, 3, 2]
     
    # Function call
    print (int(findMinValue(a, b)))
 
# This code is contributed by Chitranayal

Javascript

<script>
 
// Javascript Program to implement
// the above approach
var mod = 1000000007;
 
// Function to rearrange the second array such
// that the sum of its product of same indexed
// elements from both the arrays is minimized
function findMinValue(a, b)
{
    var n = a.length;
 
    // Stores (i - 1) * (n - i) * a[i]
    // for every i-th element
    var pro = Array(n);
 
    for(var i = 0; i < n; ++i)
    {
         
        // Updating the value of pro
        // according to the function
        pro[i] = ((i + 1) * (n - i));
        pro[i] *= (1 * a[i]);
        ;
    }
 
    // Sort the array in reverse order
    b.sort((a, b) => b - a)
 
    // Sort the products
    pro.sort((a, b) => a - b)
 
    var ans = 0;
    for(var i = 0; i < n; ++i)
    {
         
        // Updating the ans
        ans += (pro[i] % mod * b[i]) % mod;
        ans %= mod;
    }
 
    // Return the ans
    return ans;
}
 
// Driver code
var a = [ 1, 2, 3 ];
var b = [ 2, 3, 2 ];
 
// Function call
document.write( findMinValue(a, b));
 
// This code is contributed by itsok
 
</script>
Producción: 

43

 

Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por dreamer07 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *