题目大意
给定两个数\(a,b\)，每次可以对两个数同时进行以下操作之一：
- 将两个数都加上1
- 将两个数都乘上2
问能否经过若干次操作，使两个数同时等于\(a',b'\)，求最小的操作次数，或不可能完成。
解法
考虑一个数的情形，可以算出，假如我们进行了\(k\)次乘二操作完成，则有：
\[a' = 2^k a + 2^k x_0 + 2^{k-1} x_1 + \ldots 2^0 x_k\]可以发现，如果题目的要求可以实现，那么\(\exists k \in N\)，使得\(a' = 2^k a + 2^k x_0 + 2^{k-1} x_1 + \ldots 2^0 x_k\)，同时，\(b' = 2^k b + 2^k x_0 + 2^{k-1} x_1 + \ldots 2^0 x_k\)
枚举\(k\)，通过二进制可以知道，\(x_1,x_2,\ldots,x_k\in \{0, 1\}\)，于是可以贪心的算出答案.
Code
class DoubleOrOneEasy {
public:
int minimalSteps(int _a, int _b, int _newA, int _newB) {
long long a(_a), b(_b), newA(_newA), newB(_newB);
int ans = 0x7fffffff;
int cnt = 0;
while (a <= newA && b <= newB) {
if (newA - a == newB - b) {
int tmp = 0;
long long rem = newA - a;
for (int i = cnt; i >= 0; i--) {
tmp += (rem >> i);
rem &= ((1 << i) - 1);
}
ans = min(ans, tmp + cnt);
}
a *= 2;
b *= 2;
cnt++;
}
return ans == 0x7fffffff ? -1 : ans;
}
};
Level Upper 2016 - TopCoder 250 : 4 / 5