http://community.topcoder.com/stat?c=problem_statement&pm=12790&rd=15708
这道题只有两个操作，一是加一，二是数组所有元素乘以二，求最少操作次数从全0数组变成目标数组。我的方法是从目标数组反推全0数组，如果有奇数就变成偶数，全偶数就除以二。这个方法是可以过的，就是效率拙计：
import java.util.*;
public class IncrementAndDoubling
{
public int getMin(int[] A)
{
int count = 0;
int len = A.length;
while (true)
{
boolean done = true;
for (int i = 0; i < len; i++)
{
if (A[i] % 2 == 1)
{
A[i]--;
count++;
}
if (A[i] != 0)
done = false;
}
if (done) break;
for (int i = 0; i < len; i++)
{
A[i] = A[i] / 2;
}
count++;
}
return count;
}
}
但更好的方法如标程里所介绍，观察到除以2就是移位，0和1的转换。那么最后的结果其实是数组里所有二进制1的个数，加上最长的二进制表示长度。
int getMin(vector<int> desiredArray)
{
int mx = 1; // '0' has length 1
int sum = 0;
for (int x: desiredArray) {
int c = 0;
// extract bits from x:
while (x > 0) {
c++;
sum += x % 2; //the last bit
x /= 2;
}
mx = std::max(mx, c);
// the number c of bits is wrong for '0', but it doesn't matter
// because mx is initially set to 1.
}
return mx - 1 + sum;
}