重新排列一个数组，以使连续一对元素的乘积之和最小，使用C++编写

我们有一个正整数类型的数组，假设是arr[]，大小任意。任务是重新排列数组，使得当我们将一个元素与其相邻元素相乘，然后将所有结果元素相加时，返回最小的和。

让我们看看不同的输入输出情况：

输入 - int arr[] = {2, 5, 1, 7, 5, 0, 1, 0}

输出 - 重新排列数组以最小化和，即连续一对元素的乘积为：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。

立即学习“C++免费学习笔记（深入）”；

输入 - int arr[] = {1, 3, 7, 2, 4, 3}

输出 - 重新排列数组以最小化和，即连续一对元素的乘积为：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方法对数组进行排序，将数组和数组的大小传递给sort函数。

  

  Dora

  创建令人惊叹的3D动画网站，无需编写一行代码。

  下载

• 声明一个整数变量，并将其设置为调用函数的返回值。

Example

#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