牛客 QQ8 数字转换机

标签: 牛客腾讯题库 发布于:2022-03-03 17:20:29 编辑于:2022-03-03 17:21:08 浏览量:325

概述

https://www.nowcoder.com/practice/e870b63e149341c8b6441bc9ebf963d6

动态规划法

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <climits>

using namespace std;

unordered_map<int, unordered_map<int, int>> dp;
int A, B;
int helper(int a, int b) {
    if (a == A && b == B) return 0;
    if (a == A || b == B) return INT_MAX;
    if (a > A || b > B) return INT_MAX;
    if (dp[a].count(b)) return dp[a][b];
    int count = 0;
    count = min(helper(a+1, b+1), helper(2*a, 2*b));
    if (count != INT_MAX) count += 1;
    dp[a][b] = count;
    return count;
}

int main() {
    int a, b;
    cin >> a >> b >> A >> B;
    auto ans = helper(a, b);
    if (ans != INT_MAX) cout << ans;
    else cout << -1;
}

贪心法

来源于牛客网章闰水的评论

我们考虑数字的二进制形式。

    • 1 对应着最后一位为 0 时将其置 1,为 1 时进位置 0;
    • 2 对应着左移一位。

贪心指的是:如果先加后乘与先乘后加都可以时,一定是先加后乘操作次数较少。

对于 a 和 A,我们先使得 a 与 A 的前面对齐,所以操作次数为 A 右移动到与 a 同位数时 A 减 a 的差, 如果是负数说明 a 的前缀比 A 大,此时不可能有解;

之后的话,就是差的位数加上其中 1 的个数。

遗憾的是,由于是两个数,我们不能直接算,必须进行模拟,以确认 b 能否同时达到 B。

为什么如果 a 取贪心解时 b 不 work 就一定不行?

有点麻烦,不搞了。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/