题解 | #神奇天平#

题目中，当 $m=2m\; =\; 2$ 时，首先将原来的物品分成了 3 份，只称量了一次就找到了物品在哪，所以我们不妨大胆猜测，称量 $nn$ 个物品只需要将其一直分为 $m+1m\; +\; 1$ 份称量可以使得最坏情况下最优

下面简单的给出不太严谨的证明：

如果我们将其分为 $m+1m\; +\; 1$ 份，那么我们可以称量一次就能找到最重的物品在哪一堆，并且最坏情况下那一堆有 $n\mathrm{/}(m+1)+1n\; /\; (m\; +\; 1)\; +\; 1$ 个物品，这里读者可以手推一下，就不详细展开了。那么，我们每操作一步至少可以将 $nn$ 缩小到 $1\mathrm{/}m1\; /\; m$ (这里不能等于)

如果我们将其分为 $m+2m\; +\; 2$ 份，那么我们最坏需要测量 2 次，并且最坏情况下那一堆有 $n\mathrm{/}(m+2)+1n\; /\; (m\; +\; 2)\; +\; 1$ 个物品。也就是说，我们平均每步至少将 $nn$ 缩小到 $2\mathrm{/}(m+1)2\; /\; (m\; +\; 1)$

其他情况也是一样的道理，总之，其他情况推出来最坏的情况一定不如将 $nn$ 分成 $m+1m\; +\; 1$ 份优

代码：

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49341752