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>
43
Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)