题解：P10892 SDOI2024

Just_a_oler · 2024-08-21 20:59:42 · 题解

题目其实很简单,其实只需要模拟即可
如果 n 是奇数,纠结次数cnt加一,然后就要比较:

因为题目要求最小纠结次数,所以我们要让n尽量为偶数。

接下来会有三种情况:
1.如果\frac{n - 1}{2} 为偶数,n = n - \frac{n - 1}{2}。
2.如果\frac{n + 1}{2} 为偶数,n = n - \frac{n + 1}{2}。
3.如果以上两种情况都为偶数,随便选一个即可。

有了思路后代码就很简单了:

#include <iostream>

using namespace std;

int main() {
    int t = 0;
    long long arr[500010] = {};
    cin >> t;
    for (int i = 0; i < t; ++i) cin >> arr[i];
    for (int i = 0; i < t; ++i) {
        long long n = arr[i], ans = 0;
        while (n > 0) {
            if (n % 2 != 0) {
                if ((n - ((n - 1) / 2)) % 2 == 0) n -= (n - 1) / 2;
                else if ((n - ((n + 1) / 2)) % 2 == 0) n -= (n + 1) / 2;
                else n -= (n - 1) / 2;
                ++ans;
            } else n /= 2;
        }
        cout << ans << endl;
    }    
    return 0;
}

十年OI一场空,不开long long见祖宗!!!