2023-02-15：商场中有一展柜A，其大小固定，现已被不同的商品摆满， 商家提供了一些新商品B，需要对A中的部分商品进行更新替换， B中的商品可以自由使用，也就是可以用B中的任何商品替换A中的任何

2023-02-15：商场中有一展柜A，其大小固定，现已被不同的商品摆满，
商家提供了一些新商品B，需要对A中的部分商品进行更新替换，
B中的商品可以自由使用，也就是可以用B中的任何商品替换A中的任何商品，
A中的商品一旦被替换，就认为消失了！而不是回到了B中！
要求更新过后的展柜中，商品严格按照价格由低到高进行排列，
不能有相邻商品价格相等的情况，
A[i]为展柜中第i个位置商品的价格，B[i]为各个新商品的价格。
求能够满足A中商品价格严格递增的最小操作次数，若无法满足则返回-1。

答案2023-02-15：

动态规划。从左往右模型。

代码用rust编写。代码如下：

fn main() {

    let mut a1 = vec![1, 8, 3, 6, 9];

    let mut b1 = vec![1, 3, 2, 4];

    println!("{}", min_swaps(&mut a1, &mut b1));

    let mut a1 = vec![4, 8, 3, 10, 5];

    let mut b1 = vec![1, 3, 2, 4];

    println!("{}", min_swaps(&mut a1, &mut b1));

    let mut a1 = vec![1, 8, 3, 6, 9];

    let mut b1 = vec![4, 3, 1];

    println!("{}", min_swaps(&mut a1, &mut b1));

}

// 可以用B里的数字，替换A里的数字，想让A严格递增

// 返回至少换几个数字

fn min_swaps(aa: &mut Vec<i32>, bb: &mut Vec<i32>) -> i32 {

    // 根据题意，B里的数字随意拿

    // 所以B里的数字排序，不会影响拿

    // 同时，A如果从左往右考虑，依次被B替换上去的数字，肯定是从小到大的

    // 这是一定的！比如B = {5,3,2,9}

    // 可能先用5替换A的某个左边的数，再用2替换A的某个右边的数吗？不可能

    // 所以将B排序

    bb.sort();

    let ans = process(aa, bb, 0, 0, 0);

    return if ans == i32::MAX { -1 } else { ans };

}

// 参数解释：

// A[0...ai-1]范围上已经做到升序了

// 接下来请让A[ai....]范围上的数字做到升序

// 之前的过程中，B里可能已经拿过一些数字了

// 拿过的数字都在B[0...bi-1]范围上，不一定都拿了

// 但是最后拿的数字一定是B[bi-1]

// 如果想用B里的数字替换当前的A[ai]，请在B[bi....]范围上考虑拿数字

// pre : 表示之前的A[ai-1]被替换了没有，

// 如果pre==0，表示A[ai-1]没被替换

// 如果pre==1，表示A[ai-1]被替换了，被谁替换的？被B[bi-1]替换的！

// 返回值：让A[ai....]范围上的数字做到升序，最少还要在B[bi...]上拿几个数字

// 如果返回值是Integer.MAX_VALUE，表示怎么都做不到

// 这就是一个三维动态规划，自己改！

// ai 是N范围

// bi 是M范围

// pre 只有0、1两种值

// 所以时间复杂度O(N*M*logM)

// 这个logM怎么来的，二分来的，看代码！

fn process(aa: &mut Vec<i32>, bb: &mut Vec<i32>, ai: i32, bi: i32, pre: i32) -> i32 {

    if ai == aa.len() as i32 {

        return 0;

    }

    // 之前的数是什么

    let pre_num: i32;

    if ai == 0 {

        pre_num = i32::MIN;

    } else {

        if pre == 0 {

            pre_num = aa[(ai - 1) as usize];

        } else {

            pre_num = bb[(bi - 1) as usize];

        }

    }

    // 可能性1，搞定当前的A[ai]，不依靠交换

    let p1 = if pre_num < aa[ai as usize] {

        process(aa, bb, ai + 1, bi, 0)

    } else {

        i32::MAX

    };

    // 可能性2，搞定当前的A[ai]，依靠交换

    let mut p2 = i32::MAX;

    // 在B[bi....]这个范围上，找到>preNum，最左的位置

    // 这一步是可以二分的！因为B整体有序

    let near_more_index = bs(bb, bi, pre_num);

    if near_more_index != -1 {

        let next2 = process(aa, bb, ai + 1, near_more_index + 1, 1);

        if next2 != i32::MAX {

            p2 = 1 + next2;

        }

    }

    return get_min(p1, p2);

}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {

    if a < b {

        a

    } else {

        b

    }

}

// 在B[start....]这个范围上，找到>num，最左的位置

fn bs(bb: &mut Vec<i32>, start: i32, num: i32) -> i32 {

    let mut ans = -1;

    let mut l = start;

    let mut r = bb.len() as i32 - 1;

    let mut m: i32;

    while l <= r {

        m = (l + r) / 2;

        if bb[m as usize] > num {

            ans = m;

            r = m - 1;

        } else {

            l = m + 1;

        }

    }

    return ans;

}

2023-02-15：商场中有一展柜A，其大小固定，现已被不同的商品摆满， 商家提供了一些新商品B，需要对A中的部分商品进行更新替换， B中的商品可以自由使用，也就是可以用B中的任何商品替换A中的任何的相关教程结束。