题解 P7579 - n 个球找两个同重轻球
WYXkk
·
·
题解
提供一个奇怪的做法（
首先把球均分成三份 A,B,C，如果球数不是 3 的倍数就记剩下的一或二个为一份 D。
用 w(X) 表示 X 中球的总重。
由于轻球只有两个，故 A,B,C 的重量不会不全相等（否则至少 0+1+2=3 个轻球）。
所以，可以用两次比较得到 A,B,C 的轻重关系。（如果 w(A)\neq w(B),w(B)\neq w(C) 则由上有 w(A)=w(C)）
-
情况一：w(A)=w(B)=w(C)
可以推出轻球全在 D 中。而 D 中至多有两个球，那么就做完了。
-
情况二：w(A)=w(B)>w(C)
可以推出 A,B 中都没有轻球，这样只需要递归找 C\cup D 中的两个轻球。
-
情况三：w(A)>w(B)=w(C)
可以推出 B,C 中各有一个轻球。一堆球中找一个轻球是经典小学奥数题（均分为三份，比较其中个数相等的两份，相等则轻球在剩下一组，否则在两组中较轻的那组，如此递归，只需要 \lceil\log_3 n\rceil 次称量，且这是理论下界）。
递归边界：
-
-
-
- $w(a)=w(b)
- $w(a)\neq w(b)
答案为 a,b 中轻的那个和 c,d 中轻的那个。
-
- $w(a,b)=w(c,d)
答案为 a,b 中轻的那个和 c,d 中轻的那个。
用 3 个球的方法找到 c,d,e 中的两个轻球。
经过计算，n\le 500 时这种方法不会使用超过 12 次称量。
写起来可能巨大复杂，所以代码咕了 参考实现（与 @九九九九 的方法进行了结合）
我枚举了 $2\le n\le10^7$，得到了一个表：
| 最坏情况下的称量次数 | 为 $f(n)$ 的 $n$ 的个数 | 为 $f(n)+1$ 的 $n$ 的个数 | 为 $f(n)+2$ 的 $n$ 的个数 | 总计 |
| -------------------------------------------------------- | ----------------------- | ------------------------- | ------------------------- | --------- |
| @[九九九九](https://www.luogu.com.cn/user/151475) 的方法 | $7$ | $7910750$ | $2089242$ | $9999999$ |
| 我的方法 | $1316554$ | $5711715$ | $2971730$ | $9999999$ |
| 以上两者的结合 | $5519262$ | $4480737$ | $0$ | $9999999$ |
以及极其低效的 std（改进后）：[8,87284,406516,911635,1494401,1890585,1895631,1523493,984298,509563,209455,67290,16482,2962,367,28,1] 的第 $x$ 项（$8$ 是第 $0$ 项）是 $2\le n\le 10^7$ 中最坏情况下称量次数为 $f(n)+x$ 的 $n$ 的个数。也就是最多会到使用 $f(n)+16$ 次称量……
我猜测有一部分 $n$ 确实没有卡到 $f(n)$ 次的方法。
另外，我怀疑，这玩意在 $n$ 比较大的时候，最小称量次数还是个 open problem……