配列を再配置して、C++の連続するペア要素の積の合計を最小化します

正の整数型の配列、たとえば、任意のサイズのarr[]が与えられます。タスクは、要素に代替要素を乗算し、結果のすべての要素を加算すると、最小の合計が返されるように配列を再配置することです。

このためのさまざまな入出力シナリオを見てみましょう-

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

出力 −合計を最小化するための配列の再配置、つまり、連続するペア要素の積の7は次のとおりです。70 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は次のとおりです。71 4 2 3 3

説明 −サイズ6の整数配列が与えられます。次に、配列を再配置します。つまり、7 1 4 2 3 3.戻りの最小合計、つまり7 * 1 + 4 * 2 + 3 * 3 =7+8かどうかを確認します。 + 9=24。

以下のプログラムで使用されているアプローチは次のとおりです

• 整数型要素の配列を入力し、配列のサイズを計算します。

• 配列と配列のサイズをsort関数に渡すことにより、C++STLのsortメソッドを使用して配列をソートします。

• 整数変数を宣言し、functionRearrange_min_sum（arr、size）

  を呼び出して設定します。

• 関数Rearrange_min_sum（arr、size）

  の内部

  • 変数を作成します。たとえば、整数変数を格納する「偶数」および「奇数」タイプの型ベクトルを作成します。

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

  • iがサイズより小さくなるまでiから0までループFORを開始します。ループ内で、iがサイズ/2未満であるかどうかを確認してからarr[i]を奇数ベクトルELSEにプッシュし、arr[i]を偶数ベクトルにプッシュします

  • even.begin（）、even.end（）、greater （）。

    を渡して、sortメソッドを呼び出します。

  • iがeven.size（）未満になるまで、ループFORをiから0まで開始します。ループ内で、arr [temp++]をeven[j]に、arr [temp++]をodd[j]に、totalをtotal +even [j] * odd [j]

    に設定します。

  • 合計を返す

• 結果を印刷します。

例

#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