题解：P11455 [USACO24DEC] Cowdepenence G

Istruggle · 2025-05-26 09:40:18 · 题解

对于每个 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} 时。