腾讯9月13号数字转换机的题解，大家帮忙看看对不对。
【题目】
大意就是现在给a b A B 四个整数，每次可以对a b同时做一个+1操作或一个*2操作，问经过多少次操作之后a转化为A，同时b转为B。求操作的最小次数，如果不能转换就输出-1。
【思路】
其实首先可以进行一个公式转换。
假设总共进行了n次*2操作， m次+1操作，第i次+1操作后面进行了ki次*2操作。那么：
A = a*2n + 2k1 + … + 2km
B = b*2n + 2k1 + … + 2km, 其中，n >= k1 >= k2 >= … >= km >= 0
例如，假设a=101，
((a+1+1)*2+1)*2+1 =((101 + 1 + 1)*2 +1)*2 + 1 = 101 * 2 * 2 + 1 * 2 * 2 + 1 * 2 *2 + 1 * 2 + 1 = a * 22+22+22+21+20
n=2, m=4, k1=2, k2=2, k3=1, k4=0
有了这个公式就好办了，只需要枚举n的值，然后判断 A - a*2n == B - b*2n ，再计算m的值即可。
#include<iostream>
#include<cmath>
#include<climits>
using namespace std;
int calculateM(int remain, int n)
{
int m = 0;
do
{
m += remain / (1 << n);
remain = remain % (1 << n);
n--;
}while(n >= 0 && remain > 0);
return m;
}
int findMin(int a, int b, int A, int B)
{
int maxMulti = min((int)(log(((double)A)/a)/log(2.0)),(int)(log(((double)B)/b)/log(2.0)));
int min = INT_MAX;
for(int n = maxMulti; n >= 0; --n)
{
if(A - (a << n) == B - (b << n))
{
int m = calculateM(A - (a << n), n);
min = m + n < min ? m + n : min;
}
}
if(min == INT_MAX)
return -1;
return min;
}
int main()
{
int a, b, A, B;
cin >> a >> b >> A >> B;
cout << findMin(a,b,A,B) << endl;
return 0;
}
搜狐畅游公司福利 901人发布
查看8道真题和解析