题解：P10892 SDOI2024

· · 题解

这道题其实十分简单。

题目大意：

就是给你一个数字，当它是偶数时，就除以 2，当它是奇数时就分为两种情况：\frac{n-1}{2} 或 \frac{n+1}{2} ，问最少会碰到几次是奇数的情况。

做法：

样例都不过的做法：

思路：

考虑 \frac{n-1}{2} 比 \frac{n+1}{2} 小，那碰到奇数的概率就小，于是当是奇数时就将它变为 \frac{n-1}{2} 。

代码：

由于连样例都不过，所以就不放代码了。

问题所在：

很明显，这样有个很大的问题，你每次将这个数变为 \frac{n-1}{2} ，但不能保证变成的这个数是偶数（这样就不是最小了）。

样例中的 7 就是个很好的例子：\frac{7-1}{2} 后，答案为 3。而 \frac{7+1}{2} 后，答案为 4 。很明显，我们如果选 \frac{n-1}{2} 很有可能就会导致答案不是最小的。

正确做法：

思路：

考虑如何减小变成奇数的次数，那么我们就在每次变成奇数时，判断一下 \frac{n-1}{2} 和 \frac{n+1}{2} 哪个式子可以让数变成偶数，我们就选哪个。

证明：

不难发现，如果我们转换成了偶数，那么它的下一步变化成的数还是偶数，但如果你这一步转换成了奇数，那么下一步还得是奇数，所以说肯定不是最小的。

代码：

#include<bits/stdc++.h>
using namespace std;
long long ans;
long long n;
int T;
int main(){
    cin>>T;
    while(T--){
        ans=0;
        cin>>n;
        while(n){
            if(n%2==1){
                ans++;
                if(((n-1)/2)%2!=0){
                    n=(n+1)/2;
                }
                else{
                    n=(n-1)/2;
                }

            }
            else{
                n=n/2;
            }
        }
        cout<<ans<<"\n";
    }

}