牛客小白月赛32 C题

解题思路：对于输入的数字a可以将其看成a个1，如果可以对1进行合并成2,2合并成4，以此类推，能尽量多的合并则可以使得减去的次数最少。对于第一次循环，如果a是奇数则可以将a-1后的1全部合并为2，等价于第一次减去1后，下次减去的必是2，如果a是偶数则将a-2后面的1全部合并为2，等价于第一次减去1，第二次减去1,第三次减去2。处理完后将a除以2，继续进行循环。最后即可求得最优解。这个方法好像可以推广每次减的数字都必须和上一次相同或者是上一次的n倍（我乱说的。

#include<bits/stdc++.h> 
using namespace std;
#define ll long long 

int main(){
    int testcase;
    cin>>testcase;
    while(testcase--){
        ll a;
        cin>>a;
        ll ans=0;
        while(a!=0){
            if(a%2==1){
                a=(a-1)/2;ans++;
            }
            else {
                a=(a-2)/2;ans+=2;
            }
        }
        cout<<ans<<endl; 
    }
    return 0;
}