大妈一开始手上有x个鸡蛋，她想让手上的鸡蛋数量变成y，
操作1 : 从仓库里拿出1个鸡蛋到手上，x变成x+1个，
操作2 : 如果手上的鸡蛋数量是3的整数倍，大妈可以直接把三分之二的鸡蛋放回仓库，手里留下三分之一。
返回从x到y的最小操作次数。
1 <= x,y <= 10^18。
平凡解limit。当x大于y时，x加1到能被3整除时，然后整除，一直到等于y为止。
代码用rust编写。代码如下：
use rand::Rng;
fn main() {
let max = 3000;
let test_time = 500;
println!("测试开始");
for _ in 0..test_time {
let x = rand::thread_rng().gen_range(0, max) + 1;
let y = rand::thread_rng().gen_range(0, max) + 1;
let ans1 = min_times1(x, y);
let ans2 = min_times2(x, y);
if ans1 != ans2 {
println!("出错了!");
println!("x = {}", x);
println!("y = {}", y);
println!("{}", ans1);
println!("{}", ans2);
break;
}
}
println!("测试结束");
}
// 彻底贪心！
fn min_times1(x: i32, y: i32) -> i32 {
if x <= y {
return y - x;
}
// 0 0
// 1 2
// 2 1
let mod0 = x % 3;
// 鸡蛋拿到3的整数倍，需要耗费的行动点数
let need = if mod0 == 0 {
0
} else {
if mod0 == 1 {
2
} else {
1
}
};
return need + 1 + min_times1((x + 2) / 3, y);
}
fn min_times2(x: i32, y: i32) -> i32 {
if x <= y {
return y - x;
}
let limit = min_times1(x, y);
let mut dp: Vec<Vec<i32>> = vec![];
for i in 0..x + limit + 1 {
dp.push(vec![]);
for _ in 0..limit + 1 {
dp[i as usize].push(0);
}
}
return process(x, y, 0, limit, &mut dp);
}
// 当前鸡蛋数量cur，目标aim
// 之前已经用了多少行动点，pre
// limit : 一定行动点，超过limit，不需要尝试了！
fn process(cur: i32, aim: i32, pre: i32, limit: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
if pre > limit {
return 2147483647;
}
if dp[cur as usize][pre as usize] != 0 {
return dp[cur as usize][pre as usize];
}
let mut ans = 0;
if cur == aim {
ans = pre;
} else {
let p1 = process(cur + 1, aim, pre + 1, limit, dp);
let mut p2 = 2147483647;
if cur % 3 == 0 {
p2 = process(cur / 3, aim, pre + 1, limit, dp);
}
ans = get_min(p1, p2);
}
dp[cur as usize][pre as usize] = ans;
return ans;
}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}执行结果如下：
