หาจำนวนการรวม (Merge) น้อยที่สุดเพื่อทำให้อาร์เรย์เป็นพาลินโดรมใน C++

คำอธิบายปัญหา

ได้รับอาร์เรย์ arr[] ขนาด n ที่ประกอบด้วยจำนวนบวก ต้องการหา จำนวนการดำเนินการ Merge น้อยที่สุด เพื่อทำให้อาร์เรย์กลายเป็น พาลินโดรม (Palindrome)

อาร์เรย์พาลินโดรม คือ อาร์เรย์ที่สมาชิกตำแหน่ง i และ n-i-1 มีค่าเท่ากันทุกคู่ (เหมือนสตริงพาลินโดรม)

การดำเนินการที่อนุญาต:

มีเพียงการ Merge (รวม) เท่านั้น ซึ่งจะนำสมาชิกตำแหน่ง i และ i+1 มาบวกกัน แล้วแทนที่ตำแหน่ง i (อาร์เรย์จะสั้นลง 1 ตัว)

ตัวอย่าง

Input: arr[] = {4, 1, 7, 6, 1, 5}

Output: 2

คำอธิบาย: ต้องใช้ 2 ครั้งของการ Merge:

1. รวม index 0 และ 1 → {5, 7, 6, 1, 5}
2. รวม index 2 และ 3 → {5, 7, 7, 5} (เป็นพาลินโดรมแล้ว)

แนวทางแก้ปัญหา (Two Pointers)

ใช้สองตัวชี้ (pointers) คือ start (หน้า) และ end (หลัง) แล้ววนลูปจนกว่า start >= end:

• ถ้า arr[start] == arr[end]: เงื่อนไขพาลินโดรมเป็นจริง → start++, end--
• ถ้า arr[start] > arr[end]: ต้อง Merge ด้านหลัง → end--, arr[end] += arr[end+1], mergeCount++
• ถ้า arr[start] < arr[end]: ต้อง Merge ด้านหน้า → start++, arr[start] += arr[start-1], mergeCount++

คืนค่า mergeCount เมื่อ start == end

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

#include <iostream>
using namespace std;

int findMergeCount(int arr[], int n) {
    int mergeCount = 0;
    int start = 0;
    int end = n - 1;
    
    while (start <= end) {
        if (arr[start] == arr[end]) {
            start++;
            end--;
        } else if (arr[start] > arr[end]) {
            end--;
            arr[end] += arr[end + 1];
            mergeCount++;
        } else {
            start++;
            arr[start] += arr[start - 1];
            mergeCount++;
        }
    }
    return mergeCount;
}

int main() {
    int arr[] = {4, 1, 7, 6, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The minimum number of merge operations required to make the array palindrome is " << findMergeCount(arr, n);
    return 0;
}

ผลลัพธ์

The minimum number of merge operations required to make the array palindrome is 2