P10892 SDOI2024 题解

【题意简述】

你有一个数字 \(n\)，每次操作将 \(n/2\)，如果 \(n\) 是一个奇数，你会纠结是向上取整还是向下取整。

问你最少纠结多少次。

多组数据。

【思路】

为了方便起见，我们在二进制下重新审视这个题目：

• 在二进制下，一个数除以 \(2\) 等同于右移一位。
  • 默认向下取整，因为右移会舍弃最后一位，可能使答案偏小。
  • 如果要向上取整，就将结果加一。

题目就变成了：

你有一个数字 \(n\)，每次操作将 \(n\) 右移一位。

如果 \(n\) 是一个奇数，你会纠结是否将结果加一。

问你最少纠结多少次。

分类讨论：

• \(n\) 是偶数：说明 \(n\) 最后一位是 \(0\)，直接右移。
• \(n\) 是奇数：说明 \(n\) 最后一位是 \(1\)：
  • 如果 \(n\) 的倒数第二位是 \(0\)，那么不选择加一，不然倒数第二位变成 \(1\)，又多一个纠结点。
  • 如果 \(n\) 的倒数第二位是 \(1\)，那么选择加一一定不劣（可以通过进位，可能少几个 \(1\)）。

膜拜一血 Shadow_T。

【Code】

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

int n,ans;
void Main(){
	ans=0;
	scanf("%lld",&n);
	while(n){
		if(n%2==0){
			n=n/2;               // n 直接除以 2
		}else
			if((n/2)&1) n=n/2+1; // n 倒数第二位是 1，进位
			else        n=n/2;   // n 倒数第二位是 0，不进位
			ans++;
		}
	}
	printf("%lld\n",ans);
}

int T;
signed main()
{
	scanf("%lld",&T);
	while(T--) Main();
	return 0;
}