Suma mínima del producto de dos arreglos

Encuentre la suma mínima de Productos de dos arrays del mismo tamaño, dado que se permiten k modificaciones en la primera array. En cada modificación, un elemento de array de la primera array se puede aumentar o disminuir en 2.
Ejemplos: 

Input : a[] = {1, 2, -3}
        b[]  = {-2, 3, -5}
           k = 5
Output : -31
Explanation:
Here n = 3 and k = 5. 
So, we modified a[2], which is -3 and 
increased it by 10 (as 5 modifications 
are allowed).
Final sum will be :
(1 * -2) + (2 * 3) + (7 * -5)
   -2    +    6    -    35
             -31
(which is the minimum sum of the array 
with given conditions)

Input : a[] = {2, 3, 4, 5, 4}
        b[] = {3, 4, 2, 3, 2}
        k = 3
Output : 25
Explanation: 
Here, total numbers are 5 and total 
modifications allowed are 3. So, modify 
a[1], which is 3 and decreased it by 6 
(as 3 modifications are allowed).
Final sum will be :
(2 * 3) + (-3 * 4) + (4 * 2) + (5 * 3) + (4 * 2)
   6    –    12    +    8    +    15   +    8
                        25
(which is the minimum sum of the array with 
given conditions)

Como necesitamos minimizar la suma del producto, encontramos el producto máximo y lo reducimos. Tomando algunos ejemplos, observamos que hacer cambios de 2*k en un solo elemento es suficiente para obtener la suma mínima. Con base en esta observación, consideramos cada elemento como el elemento en el que aplicamos todas las k operaciones y realizamos un seguimiento del elemento que reduce el resultado al mínimo.  

// CPP program to find minimum sum of product of two arrays
// with k operations allowed on first array.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum product
int minproduct(int a[], int b[], int n, int k)
{
    int diff = 0, res = 0;
    int temp;
    for (int i = 0; i < n; i++) {
 
        // Find product of current elements and update
        // result.
        int pro = a[i] * b[i];
        res = res + pro;
 
        // If both product and b[i] are negative, we must
        // increase value of a[i] to minimize result.
        if (pro < 0 && b[i] < 0)
            temp = (a[i] + 2 * k) * b[i];
 
        // If both product and a[i] are negative, we must
        // decrease value of a[i] to minimize result.
        else if (pro < 0 && a[i] < 0)
            temp = (a[i] - 2 * k) * b[i];
 
        // Similar to above two cases for positive product.
        else if (pro > 0 && a[i] < 0)
            temp = (a[i] + 2 * k) * b[i];
        else if (pro > 0 && a[i] > 0)
            temp = (a[i] - 2 * k) * b[i];
 
        // Check if current difference becomes higher than
        // the maximum difference so far.
        int d = abs(pro - temp);
        if (d > diff)
            diff = d;
    }
 
    return res - diff;
}
 
// Driver function
int main()
{
    int a[] = { 2, 3, 4, 5, 4 };
    int b[] = { 3, 4, 2, 3, 2 };
    int n = 5, k = 3;
    cout << minproduct(a, b, n, k) << endl;
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// C program to find minimum sum of product
// of two arrays with k operations allowed on
// first array.
#include <stdio.h>
#include<stdlib.h>
 
// Function to find the minimum product
int minproduct(int a[], int b[], int n, int k)
{
    int diff = 0, res = 0;
    int temp;
    for (int i = 0; i < n; i++) {
        // Find product of current elements and update
        // result.
        int pro = a[i] * b[i];
        res = res + pro;
 
        // If both product and b[i] are negative, we must
        // increase value of a[i] to minimize result.
        if (pro < 0 && b[i] < 0)
            temp = (a[i] + 2 * k) * b[i];
 
        // If both product and a[i] are negative, we must
        // decrease value of a[i] to minimize result.
        else if (pro < 0 && a[i] < 0)
            temp = (a[i] - 2 * k) * b[i];
 
        // Similar to above two cases for positive product.
        else if (pro > 0 && a[i] < 0)
            temp = (a[i] + 2 * k) * b[i];
        else if (pro > 0 && a[i] > 0)
            temp = (a[i] - 2 * k) * b[i];
 
        // Check if current difference becomes higher than
        // the maximum difference so far.
        int d = abs(pro - temp);
        if (d > diff)
            diff = d;
    }
 
    return res - diff;
}
 
// Driver function
int main()
{
    int a[] = { 2, 3, 4, 5, 4 };
    int b[] = { 3, 4, 2, 3, 2 };
    int n = 5, k = 3;
    printf("%d ",minproduct(a, b, n, k));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// Java program to find minimum sum of product of two arrays
// with k operations allowed on first array.
import java.math.*;
 
class GFG {
 
    // Function to find the minimum product
    static int minproduct(int a[], int b[], int n, int k)
    {
        int diff = 0, res = 0;
        int temp = 0;
        for (int i = 0; i < n; i++) {
 
            // Find product of current elements and update
            // result.
            int pro = a[i] * b[i];
            res = res + pro;
 
            // If both product and b[i] are negative, we
            // must increase value of a[i] to minimize
            // result.
            if (pro < 0 && b[i] < 0)
                temp = (a[i] + 2 * k) * b[i];
 
            // If both product and a[i] are negative, we
            // must decrease value of a[i] to minimize
            // result.
            else if (pro < 0 && a[i] < 0)
                temp = (a[i] - 2 * k) * b[i];
 
            // Similar to above two cases for positive
            // product.
            else if (pro > 0 && a[i] < 0)
                temp = (a[i] + 2 * k) * b[i];
            else if (pro > 0 && a[i] > 0)
                temp = (a[i] - 2 * k) * b[i];
 
            // Check if current difference becomes higher
            // than the maximum difference so far.
            int d = Math.abs(pro - temp);
            if (d > diff)
                diff = d;
        }
 
        return res - diff;
    }
 
    // Driver function
    public static void main(String[] args)
    {
        int a[] = { 2, 3, 4, 5, 4 };
        int b[] = { 3, 4, 2, 3, 2 };
        int n = 5, k = 3;
        System.out.println(minproduct(a, b, n, k));
    }
}
 
// This code is contributed by Sania Kumari Gupta

# Python program to find
# minimum sum of product
# of two arrays with k
# operations allowed on
# first array.
 
# Function to find the minimum product
def minproduct(a,b,n,k):
 
    diff = 0
    res = 0
    for i in range(n):
 
        # Find product of current
        # elements and update result.
        pro = a[i] * b[i]
        res = res + pro
 
        # If both product and
        # b[i] are negative,
        # we must increase value
        # of a[i] to minimize result.
        if (pro < 0 and b[i] < 0):
            temp = (a[i] + 2 * k) * b[i]
 
        # If both product and
        # a[i] are negative,
        # we must decrease value
        # of a[i] to minimize result.
        elif (pro < 0 and a[i] < 0):
            temp = (a[i] - 2 * k) * b[i]
 
        # Similar to above two cases
        # for positive product.
        elif (pro > 0 and a[i] < 0):
            temp = (a[i] + 2 * k) * b[i]
        elif (pro > 0 and a[i] > 0):
            temp = (a[i] - 2 * k) * b[i]
 
        # Check if current difference
        # becomes higher
        # than the maximum difference so far.
        d = abs(pro - temp)
 
        if (d > diff):
            diff = d      
    return res - diff
 
# Driver function
a = [ 2, 3, 4, 5, 4 ]
b = [ 3, 4, 2, 3, 2 ]
n = 5
k = 3
 
print(minproduct(a, b, n, k))
 
# This code is contributed
# by Azkia Anam.

// C# program to find minimum sum
// of product of two arrays with k
// operations allowed on first array.
using System;
 
class GFG {
 
    // Function to find the minimum product
    static int minproduct(int []a, int []b,
                                int n, int k)
    {
        int diff = 0, res = 0;
        int temp = 0;
        for (int i = 0; i < n; i++)
        {
     
            // Find product of current elements
            // and update result.
            int pro = a[i] * b[i];
            res = res + pro;
     
            // If both product and b[i] are
            // negative, we must increase value
            // of a[i] to minimize result.
            if (pro < 0 && b[i] < 0)
                temp = (a[i] + 2 * k) * b[i];
     
            // If both product and a[i] are
            // negative, we must decrease value
            // of a[i] to minimize result.
            else if (pro < 0 && a[i] < 0)
                temp = (a[i] - 2 * k) * b[i];
     
            // Similar to above two cases
            // for positive product.
            else if (pro > 0 && a[i] < 0)
                temp = (a[i] + 2 * k) * b[i];
            else if (pro > 0 && a[i] > 0)
                temp = (a[i] - 2 * k) * b[i];
     
            // Check if current difference
            // becomes higher than the maximum
            // difference so far.
            int d = Math.Abs(pro - temp);
            if (d > diff)
                diff = d;
        }
     
        return res - diff;
    }
     
    // Driver function
    public static void Main()
    {
        int []a = { 2, 3, 4, 5, 4 };
        int []b = { 3, 4, 2, 3, 2 };
        int n = 5, k = 3;
         
        Console.WriteLine(minproduct(a, b, n, k));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program to find minimum sum of product
// of two arrays with k operations allowed on
// first array.
 
// Function to find the minimum product
function minproduct( $a, $b, $n, $k)
{
    $diff = 0; $res = 0;
    $temp;
    for ( $i = 0; $i < $n; $i++) {
 
        // Find product of current
        // elements and update
        // result.
        $pro = $a[$i] * $b[$i];
        $res = $res + $pro;
 
        // If both product and b[i]
        // are negative, we must
        // increase value of a[i]
        // to minimize result.
        if ($pro < 0 and $b[$i] < 0)
            $temp = ($a[$i] + 2 * $k) *
                                 $b[$i];
 
        // If both product and
        // a[i] are negative,
        // we must decrease value
        // of a[i] to minimize
        // result.
        else if ($pro < 0 and $a[$i] < 0)
            $temp = ($a[$i] - 2 * $k) * $b[$i];
 
        // Similar to above two
        // cases for positive
        // product.
        else if ($pro > 0 and $a[$i] < 0)
            $temp = ($a[$i] + 2 * $k) * $b[$i];
        else if ($pro > 0 and $a[$i] > 0)
            $temp = ($a[$i] - 2 * $k) * $b[$i];
 
        // Check if current difference becomes higher
        // than the maximum difference so far.
        $d = abs($pro - $temp);
        if ($d > $diff)
            $diff = $d;
    }
 
    return $res - $diff;
}
 
    // Driver Code
    $a = array(2, 3, 4, 5, 4 ,0);
    $b =array(3, 4, 2, 3, 2);
    $n = 5;
    $k = 3;
    echo minproduct($a, $b, $n, $k);
     
// This code is contributed by anuj_67.
?>

<script>
// Javascript program to find minimum sum
// of product of two arrays with k
// operations allowed on first array.
 
// Function to find the minimum product
function minproduct(a, b, n, k)
{
    let diff = 0, res = 0;
    let temp = 0;
    for (let i = 0; i < n; i++)
    {
  
        // Find product of current elements
        // and update result.
        let pro = a[i] * b[i];
        res = res + pro;
  
        // If both product and b[i] are
        // negative, we must increase value
        // of a[i] to minimize result.
        if (pro < 0 && b[i] < 0)
            temp = (a[i] + 2 * k) * b[i];
  
        // If both product and a[i] are
        // negative, we must decrease value
        // of a[i] to minimize result.
        else if (pro < 0 && a[i] < 0)
            temp = (a[i] - 2 * k) * b[i];
  
        // Similar to above two cases
        // for positive product.
        else if (pro > 0 && a[i] < 0)
            temp = (a[i] + 2 * k) * b[i];
        else if (pro > 0 && a[i] > 0)
            temp = (a[i] - 2 * k) * b[i];
  
        // Check if current difference
        // becomes higher than the maximum
        // difference so far.
        let d = Math.abs(pro - temp);
        if (d > diff)
            diff = d;   
    }
  
    return res - diff;
}
     
// Driver code
        let a = [ 2, 3, 4, 5, 4 ];
    let b = [ 3, 4, 2, 3, 2 ];
    let n = 5, k = 3;
    document.write(minproduct(a, b, n, k));
    
   // This code is contributed by sanjoy_62.
</script>

Producción :

25

Complejidad temporal: O(n)
Espacio auxiliar: O(1)

Este artículo es una contribución de Abhishek Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.