CF1814B Long Legs 题解

发布时间 2023-12-20 09:08:38作者: jr_inf

建议降黄

\(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]\)