写点什么

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

  • 2023-02-15
    北京
  • 本文字数:1804 字

    阅读完需:约 6 分钟

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;}
复制代码



发布于: 刚刚阅读数: 3
用户头像

还未添加个人签名 2021-02-15 加入

还未添加个人简介

评论

发布
暂无评论
2023-02-15:商场中有一展柜A,其大小固定,现已被不同的商品摆满, 商家提供了一些新商品B,需要对A中的部分商品进行更新替换, B中的商品可以自由使用,也就是可以用B中的任何商品替换A中的任何_算法_福大大架构师每日一题_InfoQ写作社区