ลดผลรวมกำลังสองของคู่ที่จับคู่จาก N ตัวเลขใน C++

ปัญหา

ให้อาร์เรย์ n ตัวเลข (n เป็นเลขคู่) จับคู่เป็น n/2 คู่ ให้ผลรวมของกำลังสองของผลรวมแต่ละคู่น้อยที่สุด

Minimize: Σ (xᵢ + yᵢ)² สำหรับ n/2 คู่

ตัวอย่าง

arr = [5, 10, 7, 4]

คู่ที่เป็นไปได้:

• (5,10) และ (7,4): 15² + 11² = 225 + 121 = 346
• (5,7) และ (10,4): 12² + 14² = 144 + 196 = 340 ← น้อยที่สุด
• (5,4) และ (10,7): 9² + 17² = 81 + 289 = 370

กลยุทธ์ที่เหมาะสมที่สุด

จับคู่ค่าน้อยที่สุดกับค่ามากที่สุด (Sort แล้วจับคู่ first-last)

เหตุผล: (a+d)² + (b+c)² ≤ (a+b)² + (c+d)² เมื่อ a ≤ b ≤ c ≤ d

เพราะ (a+d)² + (b+c)² - [(a+b)² + (c+d)²] = 2(a-b)(d-c) ≤ 0

อัลกอริทึม

1. เรียงอาร์เรย์จากน้อยไปมาก
2. two pointers: start=0, end=n-1
3. จับคู่ arr[start] กับ arr[end]
4. start++, end-- จนกว่า start ≥ end

ตัวอย่างโค้ด C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long minSquareSum(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    long long minSum = 0;
    int start = 0, end = arr.size() - 1;
    
    while (start < end) {
        long long sum = arr[start] + arr[end];
        minSum += sum * sum;
        start++;
        end--;
    }
    return minSum;
}

int main() {
    vector<int> arr = {5, 10, 7, 4};
    cout << "Array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    cout << "Minimum square sum: " << minSquareSum(arr) << endl;
    
    // ทดสอบเพิ่ม
    vector<int> arr2 = {1, 2, 3, 4, 5, 6};
    cout << "Array: ";
    for (int x : arr2) cout << x << " ";
    cout << "→ Min sum: " << minSquareSum(arr2) << endl;
    // Pairs: (1,6)=49, (2,5)=49, (3,4)=49 → Total=147
    
    return 0;
}

ผลลัพธ์

Array: 5 10 7 4
Minimum square sum: 340
Array: 1 2 3 4 5 6
Minimum square sum: 147

ความซับซ้อน

• เวลา: O(n log n) จากการเรียง
• พื้นที่: O(1) เพิ่มเติม (หรือ O(n) ถ้าไม่เรียง in-place)

ขยายความ: ทำไมกลยุทธีนี้ถึง optimal?

นี่คือกรณีพิเศษของ Rearrangement Inequality: ผลรวมของผลคูณจะน้อยที่สุดเมื่อจับคู่ลำดับตรงข้าม (อันน้อยกับอันมาก)