## 题目描述 有一个整数 $n$ ，如果 $n$ 是偶数，$n$ 会减少 $\frac{n}{2}$ 但是如果 $n$ 是奇数时，可以减少 $\frac{n+1}{2}$ 也可以减少 $\frac{n-1}{2}$ 。直到 $n$ 为 $0$。求一种减少方法使得 $n$ 是奇数的次数最少。 ## 输入格式 本题有多组测试数据。 第一行一个整数 $t$。 接下来 $t$ 行，每行一个整数 $n$。 ## 输出格式 $t$ 行，每行一个整数表示最小纠结次数。 ## 样例 #1 ### 样例输入 #1 ``` 2 13 7 ``` ### 样例输出 #1 ``` 3 2 ``` 对于 $100\%$ 的数据，保证 $1\le n \le 2^{60}$，$1 \le t \le 5\times 10^5$。使用c++解决

```cpp #include <iostream> #include <vector> using ll = long long; ll minOddCount(ll n) { std::vector<ll> dp(n + 1, INT_MAX); dp[0] = 0; for (ll i = 1; i <= n; ++i) { if (i % 2 == 0) { dp[i] = dp[i / 2] + 1; } else { dp[i] = std::min(dp[(i + 1) / 2] + 1, dp[(i - 1) / 2] + 1); } } return dp[n]; } int main() { ll t; std::cin >> t; while (t--) { ll n; std::cin >> n; std::cout << minOddCount(n) << std::endl; } return 0; } ``` [2024-08-21 16:33:58 | AI写代码神器 | 229点数解答]