Минимальная сумма произведений двух массивов (a1 * a2 *… * an) + (b1 * b2 *… * bn) - PullRequest
Новая
       8

Минимальная сумма произведений двух массивов (a1 * a2 *… * an) + (b1 * b2 *… * bn)

0 голосов
/ 08 ноября 2019

Задача:

Учитывая два массива arr[] и brr[] с n элементами каждый.
Найти минимально возможную сумму произведений всехэлементы в arr и brr (arr[0]*arr[1]*arr[2]*...arr[n] + brr[0]*brr[1]*brr[2]*...brr[n]), если вам разрешено делать k модификаций. С каждой модификацией вы можете изменить значение любого элемента arr на ± 2.

Решение
Я должен сделать значение произведения 1-го массива минимальным, как этоединственный, который я могу изменить.

В Arr есть все элементы + ve. Сначала я проверяю, могу ли я создать первый элемент -ve.

Случай 1: Да, он может быть отрицательным

Если это так, я делаю его отрицательным, используя минимум k. При этом переменная prod обновляется до -1. Затем я беру абсолютные значения элементов arr и пытаюсь сделать ПРОДУКТ МАКСИМАЛЬНЫМ (подход, описанный в разделе КАК УВЕЛИЧИТЬ ПРОДУКТ), используя оставшиеся ks (максимум, потому что в итоге результат будет отрицательным).

Увеличение произведения

(Проведя некоторые наблюдения, я обнаружил, что если сумма чисел одинакова, то уменьшение разрыва увеличивает произведение.
Если сумма меньше, чем произведение, то и меньше принимает абсолютные значенияво внимание, а не в минус.
Поэтому я стремлюсь увеличивать сумму и уменьшать разрыв. Для этого я увеличиваю минимальное число на каждом шаге. Например,
1 * 5 = 5 сумма = 1 + 5 = 6 разрыв= abs (5-1) = 4
2 * 4 = 8 сум = 2 + 4 = 6 пробелов = abs (4-2) = 2
3 * 3 = 9 сум = 3 + 3 = 6 пробелов= abs (3-3) = 0

, поэтому, используя это наблюдение, я беру abs (arr [i]), то есть абсолютное значение элементов массива и
1. увеличиваем min и уменьшаем k
2. сортировка массива (минимальное значение также может быть изменено)
3. увеличение минимума и уменьшение k
Я повторяю это, пока все ksЗатем я нахожу значение умножения и использую его, чтобы найти конечный результат. )

Случай 2: Нет, оно не может быть отрицательным Здесь я пытаюсь уменьшить продукт

Уменьшить продукт

уменьшить сумму и увеличить разрыв. Для этого я беру мин на каждом шаге и уменьшаю его. 

//make the sum of product of 2 arrays minimum
#include<bits/stdc++.h>
using namespace std;

int n=5;
int arr_increase(int prod,vector<int> arr,int k)
{
    //decrease the gap
    //take the min at each step and increase it
    sort(arr.begin(),arr.end());
    while(k)
    {
        arr[0]=arr[0]+2;
        sort(arr.begin(),arr.end());
        k=k-1;
    }
    for(int i=0;i<n;i++)
    {
        prod=prod*arr[i];
    }
    return prod;
}

int arr_decrease(int prod,vector<int> arr,int k)
{
    //increase the gap
    //take the min at each step and decrease it
    while(k)
    {
        arr[0]=arr[0]-2;
        sort(arr.begin(),arr.end());

        k=k-1;
    }
    for(int i=0;i<n;i++)
    {
        cout<<"arr[i]="<<arr[i]<<endl;
        prod=prod*arr[i];
    }
    return prod;
}

int main()
{
    vector<int> arr={2, 3, 4, 5, 4};
    vector<int> brr={3, 4, 2, 3, 2};
    int k=3;
    int value;
    int mulBrr=1;

    for(int i=0;i<n;i++)
    {
        mulBrr=mulBrr*brr[i];
    }


    sort(arr.begin(),arr.end());

    if(arr[0]-(2*k)<0)//can make the first negative
    {
        while(arr[0]>=0 && k>0)
        {
            arr[0]=arr[0]-2;
            k=k-1;
        }
        int prod=-1;

        for(int i=0;i<n;i++)
        {
            if(arr[i]<0)
            {
                arr[i]=-1*arr[i];
            }
        }

        sort(arr.begin(),arr.end());

        value=arr_increase(prod,arr,k);
        cout<<"arr_increase gives "<<value<<" in block A"<<endl;
    }
    else 
    {
        int prod=1;
        //all are positive
        value=arr_decrease(prod,arr,k);
        cout<<"arr_decrease gives "<<value<<" in block B"<<endl;
    }    

   cout<<"The end result is "<<value+mulBrr<<endl;

    return 0;
}

arr_increase дает -960 в блоке A
Конечный результат -816.

Подход квопрос правильный или нет. Также есть и другие способы решения вопроса.

...