package daily.hard

import kotlin.math.min

fun main() {
    // 801. 使序列递增的最小交换次数
    // https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing/
    println(minSwap(intArrayOf(1,3,5,4), intArrayOf(1,2,3,7)))
}

fun minSwap(nums1: IntArray, nums2: IntArray): Int {
    /**
     * 1.状态定义
     * noSwapDp[]，noSwapDp[i]，表示 [0,i] 的元素，nums1 和 nums2 均已成为递增数组，且第 i 个元素没有交换的最小次数
     * swapDp[]，swapDp[i]，表示 [0,i] 的元素，nums1 和 nums2 均已成为递增数组，且第 i 个元素有交换的最小次数
     * 2.状态转移方程
     * ...nums1[i-1] nums1[i]...
     * ...nums2[i-1] nums2[i]...
     * 2.1 if (nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i]) 无需操作
     * 2.2 if (nums2[i-1] < nums1[i] && nums1[i-1] < nums2[i]) 必须操作
     * 2.3 同时满足 2.1、2.2，可以选择 操作 或者 不操作
     * 3.初始值
     * noSwapDp[0] = 0, swapDp[0] = 1
     */
    val n = nums1.size
    val noSwapDp = IntArray(n)
    val swapDp = IntArray(n)
    noSwapDp[0] = 0
    swapDp[0] = 1
    for (i in 1 until n) {
        val a1 = nums1[i-1]
        val a2 = nums1[i]
        val b1 = nums2[i-1]
        val b2 = nums2[i]
        if ((a1 < a2 && b1 < b2) && (a1 < b2 && b1 < a2)) {
            // 2.3 同时满足 2.1、2.2，可以选择 操作 或者 不操作
            // 至于要不要操作，看 noSwapDp[i-1] 和 swapDp[i-1] 哪个更小
            val min = min(noSwapDp[i-1], swapDp[i-1])
            noSwapDp[i] = min
            swapDp[i] = min + 1
        }else if (a1 < a2 && b1 < b2) {
            // 2.1 if (nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i]) 无需操作
            noSwapDp[i] = noSwapDp[i-1]
            swapDp[i] = swapDp[i-1] + 1
        }else {
            // 2.2 if (nums2[i-1] < nums1[i] && nums1[i-1] < nums2[i]) 必须操作
            noSwapDp[i] = swapDp[i-1] // 如果 i 不互换，则 i-1 必须互换
            swapDp[i] = noSwapDp[i-1] + 1 // 如果 i 互换，则 i-1 必须不互换
        }
    }
    return min(swapDp[n-1], noSwapDp[n-1])
}

fun minSwap1(nums1: IntArray, nums2: IntArray): Int {
    // 状态定义，swapDp[i] 表示在 i 位置执行交换，使得 nums1 和 nums2 在 [0,i] 的区间都严格递增的最小交换次数；
    // noSwapDp[i] 表示在 i 位置 **不** 执行交换，使得 nums1 和 nums2 在 [0，i] 的区间都严格递增的最小交换次数；
    val swapDp = IntArray(nums1.size)
    val noSwapDp = IntArray(nums1.size)

    // 初始值
    swapDp[0] = 1 // 在 0 位置交换
    noSwapDp[0] = 0 // 在 0 位置不交换

    for (i in 1 until  nums1.size) {
        if (nums1[i-1] < nums1[i] && nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i] && nums2[i-1] < nums2[i]) {
            // 两个数组，在 i-1 的位置，都比 i 位置小
            // 所以，i 位置要不要交换都行，取决于 swap[i-1] 和 noSwapDp[i-1] 哪个更小
            swapDp[i] = min(swapDp[i-1], noSwapDp[i-1]) + 1
            noSwapDp[i] = min(swapDp[i-1], noSwapDp[i-1])
        }else if (nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i]) {
            // i 位置要不要交换，取决于 i-1 位置有没有交换，如果 i-1 交换了，i 也要跟着交换
            swapDp[i] = swapDp[i-1] + 1
            noSwapDp[i] = noSwapDp[i-1]
        }else if (nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i]) {
            // i 位置要不要交换，取决于 i-1 位置有没有交换，如果 i-1 交换了，i 就不要交换
            swapDp[i] = noSwapDp[i-1] + 1
            noSwapDp[i] = swapDp[i-1]
        }
    }
    return min(swapDp[nums1.size-1], noSwapDp[nums1.size-1])
}