Cho mảng nguyên dương arr[]. Nhiệm vụ: sắp xếp mảng sao cho tổng tích các cặp phần tử liên tiếp (arr[0]*arr[1] + arr[2]*arr[3] + ...) là nhỏ nhất.
Các trường hợp đầu vào/đầu ra
Đầu vào - int arr[] = {2, 5, 1, 7, 5, 0, 1, 0}
Đầu ra - Sắp xếp tối thiểu tổng tích cặp (tổng=7): 7 0 5 0 5 1 2 1
Giải thích - Mảng size 8. Sắp xếp: 7 0 5 0 5 1 2 1. Kiểm tra: 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 tối thiểu tổng tích cặp (tổng=24): 7 1 4 2 3 3
Giải thích - Mảng size 6. Sắp xếp: 7 1 4 2 3 3. Kiểm tra: 7*1 + 4*2 + 3*3 = 7+8+9 = 24.
Phương pháp sử dụng trong chương trình dưới đây
Nhập mảng, tính size. Sắp xếp mảng tăng dần bằng sort STL.
Gọi Rearrange_min_sum(arr, size).
Trong Rearrange_min_sum:
Vector even, odd.
temp=0, total=0.
For i=0..size-1: nếu i < size/2 → odd.push_back(arr[i]); else even.push_back(arr[i]).
Sắp xếp even giảm dần (greater
()). For j=0..even.size()-1: arr[temp++] = even[j]; arr[temp++] = odd[j]; total += even[j]*odd[j].
Trả về total.
In kết quả.
Ví dụ mã
#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(arr, arr + size); int total = Rearrange_min_sum(arr, size); cout<<"Sắp xếp tối thiểu tổng tích cặp (tổng="<<total<<"): "; for(int i = 0; i < size; i++){ cout << arr[i] << " "; } return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Sắp xếp tối thiểu tổng tích cặp (tổng=7): 7 0 5 0 5 1 2 1