QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: jiangly

Posted at: 2026-04-05 16:32:45

Last updated: 2026-04-05 16:32:52

Back to Problem

题解

如果存在两个相同的数,则选择它们即可。否则所有数的总和不超过 $S=\sum_{i=1}^N\frac{1}{i}=O(\log N)$。枚举所有大小为 $\frac{N}{2}$ 的集合,如果集合数量至少是 $S\cdot 10^5+1$,则一定有两个的差不超过 $10^{-5}$。因此枚举足够多的集合,排序后判断即可。进一步发现有用的数的个数是 $O(\log( N\cdot 10^5))$,所以可以认为 $N$ 不超过 $O(\log (N\cdot 10^5))$。也就是可以认为 $N$ 不超过最小的 $N_0$ 满足 ${N_0\choose \frac{N_0}{2}}\ge H_{N_0}\cdot 10^5+1$,解出 $N_0=22$。

上面说明了当 $N\ge N_0$ 时一定有解,但我们还可以注意到,如果有解,则一定存在大小为 $\frac{N}{2}$ 的解:首先删除所有相同元素,这时大小不超过 $\frac{N}{2}$,然后添加一些相同元素即可。因此只需要枚举大小为 $\frac{N}{2}$ 的集合并排序,时间复杂度 $O(2^{N_0}\sqrt{N_0})$。也可以不排序,改为用大小为 $10^{-5}$ 的桶存放所有的总和,如果一个桶中有两个集合则找到一组解,否则最后只需要判断相邻的桶中的集合。

注意上述的复杂度都没有考虑比较,事实上存在极端数据使得两个集合的差值和 $10^{-5}$ 相差极小,但因为该题要求的是严格不超过 $10^{-5}$,理论上我们需要用精确的方法进行比较,这会带来至多 $\mathrm{poly}(N_0)$ 的因子。当然也可以先尝试用浮点数寻找不超过 $10^{-5}-\epsilon$ 的解,如果没找到再去判断浮点数差值不超过 $10^{-5}+\epsilon$ 的情况,实践中这并不会带来很大的开销。

Comments

No comments yet.