如题。这题的贡献总和上限是每个簇下界点的子树大小之和,加上(m-簇数量)* B 。
由于“子树大小之和”只能计算子树,有个 1/2 的贡献,所以形式化的为 3n2B+mB\frac{3n^2}{B}+mBB3n2+mB 左右。
假设 m=Θ(n)m=\Theta (n)m=Θ(n), 取 B=3nB=\sqrt{3n}B=3n 理论最优,为 23nn≈3.46e92\sqrt{3}n\sqrt{n} \approx 3.46e923nn≈3.46e9 ,即使考虑上一些无法整除带来的影响也远远大于 2.5e92.5e92.5e9 。
所以 6n/B 是严格上限吗?如何构造?如果可以构造这题能否 hack ?(即使不能构造很紧,现在提交的多数做法(取 B=nB=\sqrt{n}B=n )也显然远远大于限制)