P10892 SDOI2024_A 题解

· · 题解

赛时只过了这道题（我好菜），那就来水个题解吧。

思路：

首先如果 n 是个偶数，那么就直接让 n 除以 2，这个很显然，n 是奇数时，要让纠结数最少，那我们这一次就要让 n 变为偶数，众所周知，奇数减奇数等于偶数，所以我们只要判断一下 \frac{n+1}{2} 和 \frac{n-1}{2} 哪个是奇数，就让 n 减去他，然后纠结次数加一就好了。

这样的话 n 每次大约是除以了 2，时间约为 O(\log n)，T 次询问就是 O(T\log n)，时间复杂度是可以过的。

另外，鉴于 n\le 2^{60}，所以要开 long long！

代码：

#include<bits/stdc++.h>

using namespace std;

long long n,t;

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        int ans=0;
        while(n)
        {
            if(n%2==0)n/=2;//n是2的倍数，直接除以2
            else if(((n+1)/2)%2==1)ans++,n-=(n+1)/2;//判断(n-1)/2和(n+1)/2哪个是奇数
            else ans++,n-=(n-1)/2;//n+1不行就肯定是n-1了
        }
        cout<<ans<<endl;
    }
    return 0;
}