Рубрики

Минимизируйте сумму квадратов суммы элементов каждой группы, на которую разделен массив

Для данного массива, состоящего из четного числа элементов, задача состоит в том, чтобы разбить массив на группу M элементов (каждая группа должна содержать не менее 2 элементов) таким образом, чтобы сумма квадратов сумм каждой группы была минимизирована, т.е.
(sum_of_elements_of_group1) 2 + (sum_of_elements_of_group2) 2 + (sum_of_elements_of_group3) 2 + (sum_of_elements_of_group4) 2 +… .. + (sum_of_elements_of_groupM) 2

Примеры:

Input: arr[] = {5, 8, 13, 45, 6, 3}
Output: 2824
Groups can be (3, 45), (5, 13) and (6, 8)
(3 + 45)2 + (5 + 13)2 + (6 + 8)2 = 482 + 182 + 142 = 2304 + 324 + 196 = 2824

Input: arr[] = {53, 28, 143, 5}
Output: 28465

Подход: наша окончательная сумма зависит от двух факторов:

  1. Сумма элементов каждой группы.
  2. Сумма квадратов всех таких групп.

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

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

C ++

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

using namespace std;

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

unsigned long long findAnswer(int n, 

                       vector<int>& arr)

{

  

    // Сортировка массива для сопряжения элементов

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

  

    // Переменная для хранения ответа

    unsigned long long sum = 0;

  

    // Соединить наименьшее с наибольшим, второе

    // самый маленький со вторым по величине, и

    // скоро

    for (int i = 0; i < n / 2; ++i) {

        sum += (arr[i] + arr[n - i - 1])

               * (arr[i] + arr[n - i - 1]);

    }

  

    return sum;

}

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

int main()

{

    std::vector<int> arr = { 53, 28, 143, 5 };

    int n = arr.size();

    cout << findAnswer(n, arr);

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG 

{

  

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

    static int findAnswer(int n, int[] arr)

    {

  

        // Сортировка массива для сопряжения элементов

        Arrays.sort(arr);

  

        // Переменная для хранения ответа

        int sum = 0;

  

        // Соединить наименьшее с наибольшим, второе

        // самый маленький со вторым по величине, и

        // скоро

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

        {

            sum += (arr[i] + arr[n - i - 1])

                    * (arr[i] + arr[n - i - 1]);

        }

  

        return sum;

    }

  

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

    public static void main(String[] args)

    {

        int[] arr = {53, 28, 143, 5};

        int n = arr.length;

        System.out.println(findAnswer(n, arr));

    }

}

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

python3

# Python 3 реализация подхода

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

def findAnswer(n, arr):

      

    # Сортировка массива для сопряжения элементов

    arr.sort(reverse = False)

  

    # Переменная для хранения ответа

    sum = 0

  

    # Пара самая маленькая с самой большой, вторая

    # самый маленький со вторым по величине, и

    # скоро

    for i in range(int(n / 2)):

        sum += ((arr[i] + arr[n - i - 1]) * 

                (arr[i] + arr[n - i - 1]))

  

    return sum

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

if __name__ == '__main__':

    arr = [53, 28, 143, 5]

    n = len(arr)

    print(findAnswer(n, arr))

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

C #

// C # реализация подхода

using System;

  

class GFG

{

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

static int findAnswer(int n, int []arr)

{

  

    // Сортировка массива для сопряжения элементов

    Array.Sort(arr);

  

    // Переменная для хранения ответа

    int sum = 0;

  

    // Соединить наименьшее с наибольшим, второе

    // самый маленький со вторым по величине, и

    // скоро

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

    {

        sum += (arr[i] + arr[n - i - 1])

            * (arr[i] + arr[n - i - 1]);

    }

  

    return sum;

}

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

static void Main()

{

    int []arr = { 53, 28, 143, 5 };

    int n = arr.Length;

    Console.WriteLine(findAnswer(n, arr));

}
}

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

PHP

<?php
// PHP реализация подхода

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

function findAnswer($n, $arr)

{

  

    // Сортировка массива для сопряжения элементов

    sort($arr);

  

    // Переменная для хранения ответа

    $sum = 0;

  

    // Соединить наименьшее с наибольшим, второе

    // самый маленький со вторым по величине, и

    // скоро

    for ($i = 0; $i < $n / 2; ++$i

    {

        $sum += ($arr[$i] + $arr[$n - $i - 1]) * 

                ($arr[$i] + $arr[$n - $i - 1]);

    }

  

    return $sum;

}

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

$arr = array( 53, 28, 143, 5);

$n = count($arr);

echo findAnswer($n, $arr);

  
// Этот код предоставлен chandan_jnu
?>

Выход:

28465

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

Минимизируйте сумму квадратов суммы элементов каждой группы, на которую разделен массив

0.00 (0%) 0 votes