题解：P8494 [IOI 2022] 最罕见的昆虫

Xycxxx · 2026-03-03 16:38:00 · 题解

考虑先求出昆虫种数：每次加入一个数，然后询问一下看看个数有没有 >1 即可。

记昆虫种数为 sum，机器里的个数为 cnt。

考虑二分答案，想到你就能拿很高的分了。每次加一个数，然后询问一下，如果 > mid 就删掉，然后如果 sum \times mid = cnt，那么显然答案 \ge mid 。反之比 mid 小。

设二分答案内的询问次数为 T(n)，有 T(n)=n+T\left(\dfrac{n}{2}\right) = 2n。算上刚开始的一遍就是 3n。

然而其实会稍微大一些因为不一定每次都是 \dfrac{n}{2}。考虑加点优化，如果过程中已经满足 sum \times mid \le cnt，直接 break 掉，同时再加数前先把顺序随机打乱一遍，二分的右边界每次改为 \dfrac{cnt}{sum}。