Tìm số phép gộp tối thiểu để biến mảng thành palindrome trong C++

Mô tả vấn đề

Cho một mảng arr[] gồm n số dương. Nhiệm vụ là tìm số phép gộp (merge) tối thiểu để biến mảng thành palindrome.

Mảng palindrome giống như chuỗi palindrome: phần tử tại chỉ số i và n-i-1 phải giống nhau.

Ví dụ minh họa

Mảng palindrome mẫu:

{5, 1, 7, 2, 7, 1, 5}

Đầu vào:

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

Đầu ra:

2

Giải thích:

Cần 2 phép gộp:

• Gộp chỉ số 0 và 1: mảng thành {5, 7, 6, 1, 5}
• Gộp chỉ số 2 và 3: mảng thành {5, 7, 7, 5} (palindrome)

Phương pháp giải quyết

Sử dụng hai con trỏ start (đầu) và end (cuối). Duyệt cho đến khi start <= end:

• Nếu arr[start] == arr[end]: thỏa mãn điều kiện palindrome, dịch chuyển start++, end--
• Nếu arr[start] > arr[end]: gộp ở cuối (end--, arr[end] += arr[end+1]), tăng mergeCount
• Nếu arr[start] < arr[end]: gộp ở đầu (start++, arr[start] += arr[start-1]), tăng mergeCount

Trả về mergeCount khi start == end.

Chương trình minh họa

#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 << "Số phép gộp tối thiểu để mảng thành palindrome là " << findMergeCount(arr, n);
    return 0;
}

Kết quả đầu ra

Số phép gộp tối thiểu để mảng thành palindrome là 2