牛客 QQ8 数字转换机

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

概述

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 就一定不行？

有点麻烦，不搞了。

Links: 牛客-qq08-数字转换机