CF1814B Long Legs 题解

建议降黄

令 \(m\) 最后的值为 \(a\)，那么此时最佳答案为 \(a-1+ \left \lceil \frac{x}{a} \right \rceil + \left \lceil \frac{y}{a} \right \rceil\)，每次加尽量大的 \(m\) 一定最优。

当 \(x,y\) 增大时，答案显然不降，考虑找到 \(a\) 的上界。用 \(O(n)\) 的暴力跑极限数据，发现答案不到 \(45000\)，又发现 \(t \leq 100\)，所以可以对于每一个点，从 \(1\) 到上界 \(45000\) 暴力枚举 \(a\)，即可通过此题。

代码很好写，不放。

不严谨证明：

令 \(c=x+y\)（上面的 \(x,y\)）

记 \(f(x)=x-1+\frac{c}{x}\)（忽略取整符号）

则 \(f'(x)=\frac{c}{x^2}-1\)

当 \(x=\sqrt c\) 时，\(f'(x)=0\)，此时有最小值 \(f(x)=2\sqrt c-1\)。

把原来的取整符号加上，最优的 \(a\) 的值应该也在 \(\sqrt c\) 附近，实测对于所有的测试点，最优的 \(a \in [\sqrt c-100,\sqrt c+100]\)。