Tối thiểu hóa tổng bình phương cặp số C++

Đề bài

Cho mảng n phần tử (n chẵn). Tạo n/2 cặp sao cho tổng bình phương tổng mỗi cặp là nhỏ nhất.

Ví dụ: arr = {5, 10, 7, 4}. Cặp (4,10) và (5,7) cho tổng = (14)² + (12)² = 196 + 144 = 340.

Giải thuật

1. Sắp xếp mảng tăng dần
2. Ghép cặp: phần tử nhỏ nhất với lớn nhất, thứ 2 nhỏ với thứ 2 lớn...
3. Tính tổng bình phương các tổng cặp

Chứng minh: Để tối thiểu hóa Σ(aᵢ+bᵢ)² với aᵢ≤bᵢ, ghép nhỏ nhất với lớn nhất (bất đẳng thức Chebyshev/sắp xếp).

Ví dụ minh họa

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int getMinSquareSum(int *arr, int n) {
    sort(arr, arr + n);
    int minSum = 0;
    int start = 0, end = n - 1;
    while (start < end) {
        int sum = arr[start] + arr[end];
        minSum += sum * sum;
        ++start; --end;
    }
    return minSum;
}

int main() {
    int arr[] = {5, 10, 7, 4};
    cout << "Tong binh phuong nho nhat: " << getMinSquareSum(arr, SIZE(arr)) << "\n";
    return 0;
}

Kết quả

Tong binh phuong nho nhat: 340