C++で配列を並べ替えて隣接ペア要素の積の合計を最小化する方法

正の整数型の配列 arr[](任意のサイズ)が与えられたとします。課題は、配列をうまく並べ替え、隣り合う2つの要素同士を掛け合わせた積を順番に足し合わせたとき、その合計が最小になるようにすることです。

入出力シナリオの例

入力 − int arr[] = {2, 5, 1, 7, 5, 0, 1, 0}

出力 − 隣接ペア要素の積の合計が最小値(7)となるように並べ替えた配列: 7 0 5 0 5 1 2 1

説明 − サイズ8の整数配列が与えられています。これを「7 0 5 0 5 1 2 1」のように並べ替えると、合計は 7 × 0 + 5 × 0 + 5 × 1 + 2 × 1 = 0 + 0 + 5 + 2 = 7 となり、最小であることが確認できます。

入力 − int arr[] = {1, 3, 7, 2, 4, 3}

出力 − 隣接ペア要素の積の合計が最小値(24)となるように並べ替えた配列: 7 1 4 2 3 3

説明 − サイズ6の整数配列が与えられています。これを「7 1 4 2 3 3」のように並べ替えると、合計は 7 × 1 + 4 × 2 + 3 × 3 = 7 + 8 + 9 = 24 となり、これが最小値になります。

プログラムで使用するアプローチ

• 整数型の配列を入力として受け取り、配列のサイズを計算します。

• C++ STL の sort 関数に配列とそのサイズを渡し、配列を昇順にソートします。

• 整数変数を宣言し、関数 Rearrange_min_sum(arr, size) の戻り値で初期化します。

• 関数 Rearrange_min_sum(arr, size) の内部では、次の処理を行います。

  • 整数を格納するためのベクター変数(even と odd)を作成します。

  • 変数 temp と total を宣言し、0 で初期化します。

  • i を 0 から size 未満まで FOR ループで回します。ループ内では、i が size/2 より小さい場合に arr[i] を odd ベクターへ、それ以外の場合は even ベクターへ push_back します。

  • sort メソッドに even.begin()、even.end()、greater<int>() を渡して呼び出し、even を降順にソートします。

  • j を 0 から even.size() 未満まで FOR ループで回します。ループ内では、arr[temp++] に even[j] を、続けて arr[temp++] に odd[j] を代入し、total に even[j] * odd[j] を加算していきます。

  • total を返します。

• 結果を出力します。

なぜこの方法で最小化できるのか

積の合計を最小にする鍵は、「大きな値同士を掛け合わせないこと」です。配列を昇順にソートした後、大きい方の半分を降順に並べ替えて小さい方の半分と組み合わせることで、最大値×最小値、2番目に大きい値×2番目に小さい値……というペアが作られます。この貪欲な組み合わせにより、大きな値が大きな値と掛け合わされることを避け、合計を最小化できます。

例

#include <bits/stdc++.h>
using namespace std;
int Rearrange_min_sum(int arr[], int size){
    vector<int> even, odd;
    int temp = 0;
    int total = 0;
    for(int i = 0; i < size; i++){
        if (i < size/2){
            odd.push_back(arr[i]);
        }
        else{
            even.push_back(arr[i]);
        }
    }
    sort(even.begin(), even.end(), greater<int>());
    for(int j = 0; j < even.size(); j++){
        arr[temp++] = even[j];
        arr[temp++] = odd[j];
        total += even[j] * odd[j];
    }
    return total;
}
int main(){
    int arr[] = { 2, 5, 1, 7, 5, 0, 1, 0};
    int size = sizeof(arr)/sizeof(arr[0]);
    //sort an array
    sort(arr, arr + size);
    //call function
    int total = Rearrange_min_sum(arr, size);
    cout<<"Rearrangement of an array to minimize sum i.e. "<<total<<" of product of consecutive pair elements is: ";
    for(int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます。

Rearrangement of an array to minimize sum i.e. 7 of product of consecutive pair elements is: 7 0 5 0 5 1 2 1