Рубрики

Переставьте массив, чтобы минимизировать сумму произведений последовательных парных элементов

Нам дан массив четного размера, мы должны отсортировать массив таким образом, чтобы сумма произведений альтернативных элементов была минимальной, и мы должны найти эту минимальную сумму.

Примеры:

Input : arr[] = {9, 2, 8, 4, 5, 7, 6, 0}
Output : Minimum sum of the product of 
         consecutive pair elements: 74
         Sorted arr[] for minimum sum: 
         {9, 0, 8, 2, 7, 4, 6, 5}
Explanation : We get 74 using below
calculation in rearranged array.
9*0 + 8*2 + 7*4 + 6*5 = 74

Input : arr[] = {1, 2, 1, 4, 0, 5, 6, 0}
Output : Minimum sum of the product of 
         consecutive pair elements: 6
         Sorted arr[] for minimum sum: 
         {6, 0, 5, 0, 4, 1, 2, 1}
Explanation : We get 6 using below:
6*0 + 5*0 + 4*1 + 2*1 = 6

Эта проблема представляет собой вариант минимизации суммы произведений двух массивов с допустимыми перестановками .
Для перестановки массива таким образом, что мы должны получить сумму произведения последовательных пар элементов минимально, мы должны иметь все четные индексные элементы в порядке убывания и нечетные индексные элементы в порядке возрастания со всеми максимальными n / 2 элементами в качестве четного индекса и следующие n / 2 элементы с нечетным индексированием или наоборот.

Теперь, для этого наша идея проста, мы должны отсортировать основной массив и дополнительно создать два вспомогательных массива evenArr [] и oddArr [] соответственно. Мы пересекаем входной массив и помещаем n / 2 максимальных элемента в evenArr [], а следующие n / 2 — в oddArr []. Затем мы сортируем evenArr [] по убыванию и oddArr [] по возрастанию. Наконец, скопируйте элемент evenArr [] и oddArr [] элемент за элементом, чтобы получить требуемый результат и рассчитать минимально необходимую сумму.

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

C ++

// C ++ программа для сортировки массива так, чтобы
// сумма произведений альтернативного элемента
// это минимум.
#include <bits/stdc++.h>

using namespace std;

  

int minSum(int arr[], int n)

{

    // создаем evenArr [] и oddArr []

    vector<int> evenArr;

    vector<int> oddArr;

  

    // сортируем основной массив в порядке возрастания

    sort(arr, arr+n );

  

    // Помещаем элементы в oddArr [] и evenArr []

    // согласно желаемому значению.

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

    {

        if (i < n/2)

            oddArr.push_back(arr[i]);

        else

            evenArr.push_back(arr[i]);

    }

  

    // сортируем evenArr [] в порядке убывания

    sort(evenArr.begin(), evenArr.end(), greater<int>());

  

    // объединяем оба подмассива и

    // рассчитать минимальную сумму

    // произведение альтернативных элементов

    int i = 0, sum = 0;

    for (int j=0; j<evenArr.size(); j++)

    {

        arr[i++] = evenArr[j];

        arr[i++] = oddArr[j];

        sum += evenArr[j] * oddArr[j];

    }

  

    return sum;

}

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

int main()

{

    int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };

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

    cout << "Minimum required sum = " << minSum(arr, n);

    cout << "\nSorted array in required format : ";

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

       cout << arr[i] << " ";

    return 0;

}

Джава

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

  

import java.util.Arrays;

import java.util.Collections;

import java.util.Comparator;

import java.util.Vector;

  

class GFG {

  

    static int minSum(int arr[], int n) {

        // создаем evenArr [] и oddArr []

        Vector<Integer> evenArr = new Vector<>();

        Vector<Integer> oddArr = new Vector<>();

  

        // сортируем основной массив в порядке возрастания

        Arrays.sort(arr);

  

        // Помещаем элементы в oddArr [] и evenArr []

        // согласно желаемому значению.

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

            if (i < n / 2) {

                oddArr.add(arr[i]);

            } else {

                evenArr.add(arr[i]);

            }

        }

  

        // сортируем evenArr [] в порядке убывания

        Comparator comparator = Collections.reverseOrder();

        Collections.sort(evenArr,comparator);

  

        // объединяем оба подмассива и

        // рассчитать минимальную сумму

        // произведение альтернативных элементов

        int i = 0, sum = 0;

        for (int j = 0; j < evenArr.size(); j++) {

            arr[i++] = evenArr.get(j);

            arr[i++] = oddArr.get(j);

            sum += evenArr.get(j) * oddArr.get(j);

        }

  

        return sum;

    }

  
// Драйвер программы

    public static void main(String[] args) {

  

        int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};

        int n = arr.length;

        System.out.println("Minimum required sum = " 

                                  + minSum(arr, n));

        System.out.println("Sorted array in required format : ");

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

            System.out.print(arr[i] + " ");

        }

  

    }

  
}

python3

# Python 3 программа для сортировки массива таких
# эта сумма произведения альтернативного элемента
# это минимум.

def minSum(arr, n):

  

    # create evenArr [] и oddArr []

    evenArr = []

    oddArr = []

  

    # сортировать основной массив в порядке возрастания

    arr.sort()

  

    # Поместить элементы в oddArr [] и

    # evenArr [] согласно желаемому значению.

    for i in range(n):

      

        if (i < n // 2):

            oddArr.append(arr[i])

        else:

            evenArr.append(arr[i])

  

    # sort evenArr [] в порядке убывания

    evenArr.sort(reverse = True)

  

    # объединить подмассив и

    # рассчитать минимальную сумму

    # произведение альтернативных элементов

    i = 0

    sum = 0

    for j in range(len(evenArr)):

        arr[i] = evenArr[j]

        i += 1

        arr[i] = oddArr[j]

        i += 1

        sum += evenArr[j] * oddArr[j]

      

    return sum

  
Код водителя

if __name__ == "__main__":

      

    arr = [ 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 ]

    n = len(arr)

    print( "Minimum required sum ="

                      minSum(arr, n))

    print("Sorted array in required format : "

                                      end = "")

    for i in range(n):

        print(arr[i], end = " ")

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

C #

// Программа для сортировки массива так, что
// сумма произведений альтернативного элемента
// это минимум.

using System;

using System.Collections.Generic;

  

class GFG

{

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

{

    // создаем evenArr [] и oddArr []

    List<int> evenArr = new List<int>();

    List<int> oddArr = new List<int>();

    int i;

      

    // сортируем основной массив в порядке возрастания

    Array.Sort(arr);

  

    // Помещаем элементы в oddArr [] и

    // evenArr [] согласно желаемому значению.

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

    {

        if (i < n / 2) 

        {

            oddArr.Add(arr[i]);

        

        else 

        {

            evenArr.Add(arr[i]);

        }

    }

  

    // сортируем evenArr [] в порядке убывания

    evenArr.Sort();

    evenArr.Reverse();

  

    // объединяем оба подмассива и

    // рассчитать минимальную сумму

    // произведение альтернативных элементов

    int k = 0, sum = 0;

    for (int j = 0; j < evenArr.Count; j++) 

    {

        arr[k++] = evenArr[j];

        arr[k++] = oddArr[j];

        sum += evenArr[j] * oddArr[j];

    }

  

    return sum;

}

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

public static void Main() 

{

    int []arr = {1, 5, 8, 9, 6, 

                 7, 3, 4, 2, 0};

    int n = arr.Length;

    Console.WriteLine("Minimum required sum = "

                                 minSum(arr, n));

    Console.WriteLine("Sorted array in "

                    "required format : ");

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

    {

        Console.Write(arr[i] + " ");

    }

}
}

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


Выход:

Minimum required sum = 60
Sorted array in required format : 9 0 8 1 7 2 6 3 5 4 

Эта статья предоставлена Шивам Прадхан (anuj_charm) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Переставьте массив, чтобы минимизировать сумму произведений последовательных парных элементов

0.00 (0%) 0 votes