Рубрики

Минимизировать сумму массива в соответствии с заданным условием

Дан массив целых чисел A. Задача состоит в том, чтобы минимизировать сумму элементов массива, используя следующее правило:
Выберите два индекса i и j и произвольное целое число x , чтобы x был делителем A [i], и измените их следующим образом: A [i] = A [i] / x и A [j] = A [j] * х .

Примеры:

Input: A = { 1, 2, 3, 4, 5 }
Output: 14

Divide A[3] by 2 then
A[3] = 4/2 = 2,

Multiply A[0] by 2 then
A[0] = 1*2 = 2

Updated array A = { 2, 2, 3, 2, 5 }
Hence sum = 14

Input: A = { 2, 4, 2, 3, 7 }
Output: 18

Подход: если любое число делится на x, то оптимально умножить x на наименьшее число, присутствующее в массиве.

Идея состоит в том, чтобы получить минимум массива и найти делители конкретного элемента и продолжать проверять, насколько уменьшена сумма.

Ниже приведена реализация вышеуказанного подхода:

C ++

// реализация C ++
#include <bits/stdc++.h>

using namespace std;

  
// Функция для возврата минимальной суммы

void findMin(int arr[], int n)

{

    int sum = 0;

    for (int i = 0; i < n; i++)

        sum += arr[i];

  

    // сортируем массив, чтобы найти

    // минимальный элемент

    sort(arr, arr + n);

  

    int min = arr[0];

    int max = 0;

  

    for (int i = n - 1; i >= 1; i--) {

        int num = arr[i];

        int total = num + min;

        int j;

  

        // найти номер для

        // делить

        for (j = 2; j <= num; j++) {

            if (num % j == 0) {

                int d = j;

                int now = (num / d)

                          + (min * d);

  

                // Проверка к чему

                // экземпляр суммы

                // уменьшился

                int reduce = total - now;

  

                // получение максимума

                // разница

                if (reduce > max)

                    max = reduce;

            }

        }

    }

    cout << (sum - max);

}

  
// Код драйвера

int main()

{

    int arr[] = { 1, 2, 3, 4, 5 };

    int n = sizeof(arr) / sizeof(arr[0]);

    findMin(arr, n);

}

Джава

// Java реализация вышеуказанного подхода

import java.util.*;

  

class GFG 

{

      

    // Функция для возврата минимальной суммы

    static void findMin(int arr[], int n) 

    

        int sum = 0

        for (int i = 0; i < n; i++) 

            sum += arr[i]; 

      

        // сортируем массив, чтобы найти

        // минимальный элемент

        Arrays.sort(arr); 

      

        int min = arr[0]; 

        int max = 0

      

        for (int i = n - 1; i >= 1; i--) 

        

            int num = arr[i]; 

            int total = num + min; 

            int j; 

      

            // найти номер для

            // делить

            for (j = 2; j <= num; j++) 

            

                if (num % j == 0

                

                    int d = j; 

                    int now = (num / d) + 

                              (min * d); 

      

                    // Проверка к чему

                    // экземпляр суммы

                    // уменьшился

                    int reduce = total - now; 

      

                    // получение максимума

                    // разница

                    if (reduce > max) 

                        max = reduce; 

                

            

        

        System.out.println(sum - max); 

    

      

    // Код драйвера

    public static void main (String[] args) 

    

        int arr[] = { 1, 2, 3, 4, 5 }; 

        int n = arr.length; 

        findMin(arr, n); 

    }

}

  
// Этот код предоставлен AnkitRai01

python3

# Функция для возврата минимальной суммы

def findMin(arr, n):

    sum = 0

    for i in range(0, n): 

        sum = sum + arr[i]

  

    # отсортировать массив, чтобы найти

    # минимальный элемент

    arr.sort()

  

    min = arr[0]

    max = 0

  

    for i in range(n - 1, 0, -1): 

        num = arr[i]

        total = num + min

  

        # найти номер для

        # делить

        for j in range(2, num + 1): 

            if(num % j == 0):

                d = j

                now = (num // d) + (min * d)

  

                # Проверка на что

                # экземпляр суммы

                # уменьшился

                reduce = total - now

  

                # получить максимум

                # разница

                if(reduce > max):

                    max = reduce

  

    print(sum - max)

  
Код водителя

arr = [1, 2, 3, 4, 5 ]

n = len(arr)

findMin(arr, n)

  
# Этот код предоставлен Sanjit_Prasad

C #

// C # реализация вышеуказанного подхода

using System;

      

class GFG 

{

      

    // Функция для возврата минимальной суммы

    static void findMin(int []arr, int n) 

    

        int sum = 0; 

        for (int i = 0; i < n; i++) 

            sum += arr[i]; 

      

        // сортируем массив, чтобы найти

        // минимальный элемент

        Array.Sort(arr); 

      

        int min = arr[0]; 

        int max = 0; 

      

        for (int i = n - 1; i >= 1; i--) 

        

            int num = arr[i]; 

            int total = num + min; 

            int j; 

      

            // найти номер для

            // делить

            for (j = 2; j <= num; j++) 

            

                if (num % j == 0) 

                

                    int d = j; 

                    int now = (num / d) + 

                              (min * d); 

      

                    // Проверка к чему

                    // экземпляр суммы

                    // уменьшился

                    int reduce = total - now; 

      

                    // получение максимума

                    // разница

                    if (reduce > max) 

                        max = reduce; 

                

            

        

        Console.WriteLine(sum - max); 

    

      

    // Код драйвера

    public static void Main (String[] args) 

    

        int []arr = { 1, 2, 3, 4, 5 }; 

        int n = arr.Length; 

        findMin(arr, n); 

    }

}

  
// Этот код предоставлен PrinciRaj1992

Выход:

14

Рекомендуемые посты:

Минимизировать сумму массива в соответствии с заданным условием

0.00 (0%) 0 votes