P7494

· · 题解

题意：

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

思路：

小学四五年级芝士

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

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

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

当 $n-2m\leq m+1$ 时即 $n\leq3m+1$ 时就可以不用考虑 $m$ 了。即需要称 $\lceil\log_3n\rceil$ 次。 如果不符合，最坏的情况是每次只能筛掉 $2m$ 个，所以每次 $n$ 减去 $2m$ 。 即： ```cpp 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：将一处中括号改成小括号。