杂题题解

UOJ 21缩进优化
题目链接
记 \(M=\max(a_i)\)
从反面考虑，考虑 \(x\) 让答案减小的量。即为 $\sum_{i=1}^n \lfloor \frac{a_i}{x} \rfloor\times(x-1)=(x-1)\sum_{i=1}^n \lfloor \frac{a_i}{x} \rfloor$。
只需要快速计算 $S=\sum_{i=1}^n \lfloor \frac{a_i}{x} \rfloor$。
可以直接枚举 \(\lfloor \frac{a_i}{x} \rfloor\) 的值，记为 \(t\)，则 \(x\times t\le a_i< x\times t+x\)。
统计值为 \(j\) 的 \(a_i\) 的个数，再做一次前缀和，记为 \(sum\), 则每一个 \(t\) 对 \(S\) 的贡献，即为
\(t\times (sum_{x\times t+x-1}-sum_{x\times t-1})\)。
注意到 \(t\le \frac{M}{x}\)，所以对于每一个 \(x\) ，只需要枚举 \(\frac{M}{x}\) 个 \(t\)。总复杂度为
\(\sum_{x=1}^n \frac{M}{x}=\Theta(M \log M)\)

实现简单，小坑点：\(x\times t+x-1\) 可以达到 \(2\times M\)，\(sum\) 也需要算到 \(2\times M\)。