2022-06-06：大妈一开始手上有x个鸡蛋，她想让手上的鸡蛋数量变成y， 操作1 : 从仓库里拿出1个鸡蛋到手上，x变成x+1个

2022-06-06：大妈一开始手上有x个鸡蛋，她想让手上的鸡蛋数量变成y，

操作1 : 从仓库里拿出1个鸡蛋到手上，x变成x 1个，

操作2 : 如果手上的鸡蛋数量是3的整数倍，大妈可以直接把三分之二的鸡蛋放回仓库，手里留下三分之一。

返回从x到y的最小操作次数。

1 <= x,y <= 10^18。

答案2022-06-06：

平凡解limit。当x大于y时，x加1到能被3整除时，然后整除，一直到等于y为止。

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

代码语言：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
    }
}

执行结果如下：

在这里插入图片描述

左神java代码

java rust limit

0 人点赞