我们有一个正整数类型的数组，假设是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。
输入 - 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函数。
-
声明一个整数变量，并将其设置为调用函数的返回值。
Rearrange_min_sum(arr, size)
Inside the function Rearrange_min_sum(arr, size)
-
Create a variable, let's say, ‘even’ and ‘odd’ type of type vector which stores integer variables.
-
Declare a variable as temp and total and initialise it with 0.
-
Start loop FOR from i to 0 till i less than size. Inside the loop, check IF i is less than size/2 then push arr[i] to odd vector ELSE, push arr[i] to even vector
-
Call the sort method by passing even.begin(), even.end() and greater().
-
Start loop FOR from i to 0 till i less than even.size(). Inside the loop, set arr[temp++] to even[j], arr[temp++] to odd[j] and total to total + even[j] * odd[j]
-
Return total
Print the result.
Example
#include
using namespace std;
int Rearrange_min_sum(int arr[], int size){
vector 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());
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
