自动搬运

查看原文

来自洛谷，原作者为

	lfxxx But look at the time!

搬运于2025-08-24 22:30:24，当前版本为作者最后更新于2021-04-09 21:21:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

有 $n$ 个硬币，有一个重了。给你一个两边最多能称 $m$ 个硬币的天平 ，求至少称几次能保证称出来重了的那个硬币。

思路：

小学四五年级芝士

三分法：每次平均分成三堆，称一次，可以找出硬币在三堆中的一堆。

先不考虑 $m$ ，则只要称 $\lceil\log_3n\rceil$ 次即可。

接下来再考虑 $m$ ，我们可以将 $n$ 分成这三堆：

$m$ ， $m$ ， $n-2m$ 。

当 $n-2m\leq m+1$ 时即 $n\leq3m+1$ 时就可以不用考虑 $m$ 了。即需要称 $\lceil\log_3n\rceil$ 次。

如果不符合，最坏的情况是每次只能筛掉 $2m$ 个，所以每次 $n$ 减去 $2m$ 。

即：

while(n>3*m+1){
	n-=2*m;
	s++;
}

但这样做浪费了大量的时间，所以我们可以换成除法。 即 $\lfloor\dfrac{n-3m-1}{2m}\rfloor+1$ 。

此时 $n\gets n-(\lfloor\dfrac{n-3m-1}{2m}\rfloor+1)\cdot 2m$

综上，如果设 $a=\lfloor\dfrac{n-3m-1}{2m}\rfloor+1$ ，当 $n>3m+1$ ，称的次数为 $a+\lceil\log_3(n-a\cdot 2m)\rceil$ 。当 $n\leq3m+1$ 时，称的次数为 $\lceil\log_3n\rceil$ 。

注意事项：

最后算 $\log_3n$ 时，用乘法比较，因为除法会自动向下取整，并且乘法还快一些。

代码：

#include<cstdio>
int main(){
	unsigned long long n,m,s=0,a,i;
	scanf("%llu%llu",&n,&m);
    a=(n-3*m-1)/(2*m)+1;
    if(n>3*m+1){
        s=a;
        n-=a*2*m;
    }
    i=1;
    while(n>i){
		i*=3;
		s++;
	}
    printf("%llu",s);
	return 0;
}

因为内容较多，可能有错误，如果有神犇找出本蒟蒻的错误，请在评论区指出。

更新：

2021-05-30：将一处中括号改成小括号。