Chúng ta được cung cấp một mảng kiểu số nguyên dương, giả sử, arr [] có kích thước bất kỳ. Nhiệm vụ là sắp xếp lại một mảng theo cách mà khi chúng ta nhân một phần tử với phần tử thay thế của nó và sau đó cộng tất cả các phần tử kết quả thì nó sẽ trả về tổng nhỏ nhất.
Hãy để chúng tôi xem các kịch bản đầu ra đầu vào khác nhau cho việc này -
Đầu vào - int arr [] ={2, 5, 1, 7, 5, 0, 1, 0}
Đầu ra - Sắp xếp lại một mảng để tối thiểu hóa tổng, tức là 7 tích của các phần tử cặp liên tiếp là:7 0 5 0 5 1 2 1
Giải thích - chúng tôi được cung cấp một mảng số nguyên có kích thước 8. Bây giờ, chúng tôi sẽ sắp xếp lại mảng, tức là 7 0 5 0 5 1 2 1. Chúng tôi sẽ kiểm tra xem tổng trả về tối thiểu của nó, tức là 7 * 0 + 5 * 0 + 5 * 1 + 2 * 1 =0 + 0 + 5 + 2 =7.
Đầu vào - int arr [] ={1, 3, 7, 2, 4, 3}
Đầu ra - Sắp xếp lại một mảng để tổng nhỏ nhất tức là 24 tích của các cặp phần tử liên tiếp là:7 1 4 2 3 3
Giải thích - chúng ta được cung cấp một mảng số nguyên có kích thước 6. Bây giờ, chúng ta sẽ sắp xếp lại mảng, tức là 7 1 4 2 3 3. Chúng ta sẽ kiểm tra xem tổng trả về tối thiểu của nó có nghĩa là 7 * 1 + 4 * 2 + 3 * 3 =7 + 8 hay không + 9 =24.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Nhập một mảng các phần tử kiểu số nguyên và tính kích thước của một mảng.
-
Sắp xếp mảng bằng cách sử dụng phương pháp sắp xếp của C ++ STL bằng cách chuyển mảng và kích thước của mảng cho hàm sắp xếp.
-
Khai báo một biến số nguyên và đặt nó bằng lệnh gọi hàmRearrange_min_sum (arr, size)
-
Bên trong hàm Rearrange_min_sum (arr, size)
-
Tạo một biến, giả sử, loại vectơ kiểu ‘chẵn’ và ‘lẻ’ lưu trữ các biến số nguyên.
-
Khai báo một biến dưới dạng tạm thời và tổng và khởi tạo nó bằng 0.
-
Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn kích thước. Bên trong vòng lặp, hãy kiểm tra NẾU i nhỏ hơn size / 2 rồi đẩy arr [i] sang vectơ lẻ ELSE, đẩy arr [i] sang vectơ chẵn
-
Gọi phương thức sắp xếp bằng cách chuyển Even.begin (), Even.end () và lớn hơn
(). -
Bắt đầu vòng lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn chẵn.size (). Bên trong vòng lặp, đặt arr [temp ++] thành chẵn [j], arr [temp ++] thành lẻ [j] và tổng thành tổng + chẵn [j] * lẻ [j]
-
Tổng lợi nhuận
-
-
In kết quả.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau
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