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;
}
评论