题解：P11455 [USACO24DEC] Cowdepenence G

对于每个 $x$ , 显然分的越长，答案越小，同时我们发现答案具有连续性，也就是说，如果我们单独考虑每个数 对答案的贡献，那么存在区间 $[x,x']$ 答案相同，于是我们可以二分，找到对于一个 $x$ 最大的 $x'$ 进行答案的更新，并将 $x$ 赋值为 $x'+1$ 进行下一轮查找，这样的话时间复杂度为 $\mathcal{O} \left(\frac{n}{x} n\log n\right)$。直接做显然不行，我们考虑对 $x$ 进行根号分治，如果 $x \le B$ 直接暴力查找，时间复杂度 $\mathcal{O}\left(nB\right)$，如果 $x>B$ 则进行二分。由均值不等式得 $nB+\frac{n}{B} n\log n \ge 2\sqrt{nB \times \frac{n}{B} n\log n}$ , 当且仅当 $nB = \frac{n}{B} n\log n$，即 $B = \sqrt{n\log n}$ 时。