แปลง Array ให้เป็น Strictly Increasing ด้วยการเปลี่ยนค่าน้อยที่สุดใน C++

โจทย์ปัญหา

ได้รับ Array ให้เปลี่ยนค่าองค์ประกอบให้ Array กลายเป็น Strictly Increasing (แต่ละค่ามากกว่าค่าก่อนหน้าอย่างเคร่งครัด) โดยใช้ จำนวนการเปลี่ยนค่าน้อยที่สุด

ตัวอย่าง

นำเข้า: arr = {1, 2, 6, 5, 4}
ผลลัพธ์: 2
คำอธิบาย: เปลี่ยน 5→7, 4→8 ได้ {1, 2, 6, 7, 8} (เปลี่ยน 2 ตัว)

แนวคิดการแก้ปัญหา (LIS Variant)

หา Longest Increasing Subsequence (LIS) ที่เป็นไปได้โดยคำนึงถึง Index Difference:

• เงื่อนไข: arr[i] > arr[j] และ (i - j) <= (arr[i] - arr[j])
• เงื่อนไขที่ 2 หมายถึง: ระยะห่าง Index ต้อง ≤ ระยะห่าง Value (เพื่อให้เติมค่าระหว่างได้)
• คำตอบ = n - LIS_length

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

#include <bits/stdc++.h>
using namespace std;

int minChangesToIncreasing(int arr[], int n) {
    vector<int> LIS(n, 1);
    int maxLen = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && (i - j) <= (arr[i] - arr[j])) {
                LIS[i] = max(LIS[i], LIS[j] + 1);
            }
        }
        maxLen = max(maxLen, LIS[i]);
    }
    return n - maxLen;
}

int main() {
    int arr[] = {1, 2, 6, 5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minChangesToIncreasing(arr, n) << endl;  // 2
    return 0;
}

ผลลัพธ์

2

คำอธิบายเพิ่มเติม

• ความซับซ้อน: O(n²) (Standard LIS DP)
• สามารถ Optimize เป็น O(n log n) ได้ด้วย Binary Search + Fenwick Tree/Segment Tree
• เงื่อนไข (i - j) <= (arr[i] - arr[j]) รับประกันว่าสามารถเติมค่าระหว่าง arr[j] ถึง arr[i] ได้พอดีกับช่องว่าง Index
• ปัญหานี้เทียบเท่ากับ: หา Subsequence ยาวที่สุดที่ "Fix ได้" แล้วเปลี่ยนตัวอื่น

ตัวอย่างเพิ่มเติม