牛客 QQ8 数字转换机 — JustSong 的笔记

小Q从牛博士那里获得了一个数字转换机，这台数字转换机必须同时输入两个正数a和b，并且这台数字转换机有一个红色的按钮和一个蓝色的按钮：当按下了红色按钮，两个数字同时加1。当按下了蓝色按钮，两个数字同时乘2。小Q现在手中有四个整数a，b，A，B，他希望将输入的两个整数a和b变成A，B（a对应A，b对应B）。因为牛博士允许小Q使用数字转换机的时间有限，所以小Q希望按动按钮的次数越少越好。请你帮帮小Q吧。

概述

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

有点麻烦，不搞了。