有男姐姐过情人节吗

· · 题解

Update 2.17：在某一句话后面加上了句号。

Update 2.20：加了一个空格。

情人节快乐，祝大家早生贵子。

假设我们分成 k 组，每组的大小为 x 或 x+1。

那么，对于 v 个相同颜色的球，他能被合法分组当且仅当 v\bmod x\le \lfloor\dfrac{v}{x}\rfloor。

理解这个式子很简单，我们全部用大小为 x 的组可以分成 \lfloor\dfrac{v}{x}\rfloor 组，并且这些组都可以成为 x+1，也就是说除了这些组，剩下的还没有被分的球中，有 \lfloor\dfrac{v}{x}\rfloor 是可以被分到组里的，那么我们只需要计算剩下的球有 v\bmod x 个，判断一下是否够用。

一个暴力的想法是，枚举合法的 x，然后计算有多少组，显然这个 x 越大越好，这样分的组就尽可能的少。

但是枚举量是 10^9，肯定超时，那么我们就需要找其它的性质。我觉得剩下的性质还是比较难发现的，如果没有往根号这方面想的话 T_T。

假设 a_1 为 a 中最小的元素，那么对于 x\le \sqrt{a_1}，上面的式子都是成立的，这个很容易证明。

那么我们只需要考虑 x>\sqrt{a_1} 的部分，枚举量同样很大。

这就体现出一个技巧，我们不枚举 x，而是枚举 \lfloor\dfrac{a_1}{x}\rfloor 的值，通过这个值，就类似值域分块一样，确定出 x 的范围，然后再将范围中的 x 的值带进去尝试是否合法。

设这个值为 a，则有 a_1=ax+b，那么根据上述不等式，我们可以得出 b 的范围为 [0,a]。

然后就是小学的知识啦，根据 b 的范围推出 x 的范围，首先我们有 x=\dfrac{a_1-b}{a}，然后往里面套就行了。

$$ \lfloor\dfrac{a_1}{a}\rfloor-1\le x\le \lfloor\dfrac{a_1}{a}\rfloor $$ 我们惊奇的发现，对于一个 $a$，$x$ 最多只会取两个值！所以我们就在 $O(n\sqrt{V})$ 的时间复杂度下完成了本题。 当然，求出 $\max x$ 后求答案也非常简单，对于每个球，贪心考虑，我们优先用 $x+1$ 大小的集合来装，所以直接对 $x+1$ 除后向上取整就好了，因为反正我们是可以有一种合法方案的，而这个合法方案一定是一些 $x+1$ 大小的集合变成 $x$ 大小的集合，但是总集合数量是不变的。