จำนวนการสลับน้อยที่สุดเพื่อทำให้ลำดับเพิ่มขึ้นอย่างเคร่งครัดใน C++

ให้ลำดับจำนวนเต็มสองลำดับ A และ ความยาวเท่ากัน สามารถสลับ A[i] กับ B[i] ได้ (ดัชนีเดียวกัน) ต้องการหาจำนวนการสลับน้อยที่สุดที่ทำให้ ทั้งสองลำดับเพิ่มขึ้นอย่างเคร่งครัด (strictly increasing)

ตัวอย่าง: A=[1,3,5,4], B=[1,2,3,7] → 1 (สลับตำแหน่งที่ 3: A=[1,3,5,7], B=[1,2,3,4])

ขั้นตอนการแก้ปัญหา (Dynamic Programming)

1. n = A.size(), สร้างอาร์เรย์ swapCnt[n] และ noSwapCnt[n]
2. ฐาน: swapCnt[0] = 1 (สลับที่ 0), noSwapCnt[0] = 0 (ไม่สลับ)
3. วน i = 1..n-1:
   • เริ่มต้น swapCnt[i] = noSwapCnt[i] = n (ค่าสูง)
   • กรณีไม่สลับต่อจากไม่สลับ: ถ้า A[i] > A[i-1] && B[i] > B[i-1] → noSwapCnt[i] = noSwapCnt[i-1], swapCnt[i] = swapCnt[i-1] + 1
   • กรณีสลับต่อจากไม่สลับ (หรือกลับกัน): ถ้า A[i] > B[i-1] && B[i] > A[i-1] → swapCnt[i] = min(swapCnt[i], 1 + noSwapCnt[i-1]), noSwapCnt[i] = min(noSwapCnt[i], swapCnt[i-1])
4. คำตอบ = min(swapCnt[n-1], noSwapCnt[n-1])

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

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

class Solution {
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector<int> swapCnt(n), noSwapCnt(n);
        swapCnt[0] = 1; noSwapCnt[0] = 0;
        for (int i = 1; i < n; i++) {
            swapCnt[i] = n; noSwapCnt[i] = n;
            if (A[i] > A[i-1] && B[i] > B[i-1]) {
                noSwapCnt[i] = noSwapCnt[i-1];
                swapCnt[i] = swapCnt[i-1] + 1;
            }
            if (A[i] > B[i-1] && B[i] > A[i-1]) {
                swapCnt[i] = min(swapCnt[i], 1 + noSwapCnt[i-1]);
                noSwapCnt[i] = min(swapCnt[i-1], noSwapCnt[i]);
            }
        }
        return min(swapCnt[n-1], noSwapCnt[n-1]);
    }
};

int main() {
    vector<int> v1 = {1,3,5,4};
    vector<int> v2 = {1,2,3,7};
    Solution ob;
    cout << ob.minSwap(v1, v2);
}

Input

[1,3,5,4] [1,2,3,7]

Output

1