我曾经在 uoj blog 问过,非常幸运的有两个大神给了解答,但当时我对于 pengyihao's blog 中答案式子(即 $f(n)$ )的推导搞不懂(他自己也忘了)。最近有学弟问,于是证了一下。
首先考虑证明贪心法每次的决策是唯一的,即每次能选的柱子只有 $0$ 或 $1$ 个。
定义 $h(x)=\min\{a | a^2 \ge 2x+1\}$ ,那么第一个能放在 $x$ 上面的数就是 $h(x)^2-x$ 。
显然,$h(x)^2-x$ 互不相同 $(x \in N^ * )$ 和原命题等价。
考虑单调性, $h(x)^2-x$ 并不单调。
但 $h(x)$ 是单调的,对于固定的 $h(x)$,对应的 $x$ 是一个区间,因此 $h(x)^2-x$ 也是一个区间,考虑证明这些区间单调,不相交。
也就是说第 $x$ 个区间的左端点 $>$ 第 $x-1$ 个区间的右端点,即 $x^2-\max\{ i_x | h(i_{x})=x \}>(x-1)^2-\min\{ i_{x-1} | h(i_{x-1})=x-1 \}$ 。
定义 $g(x)=\lfloor \frac{x^2-1}{2} \rfloor$ ,即 $\max\{y|h(y)=x\}$ 。
则上式等价于 $x^2-g(x)>(x-1)^2-(g(x-2)+1)$ 。
化简得 $0>-2$ 。
注意到这里用到了 $g(x-2)$ ,所以 $x=2$ 要特判:$3>0$。
所以得证。
同时可以发现每两个区间之间恰好隔着一个数,所以所有没柱子可选的数为 $\{x^2-g(x)-1 | x \ge 2 \} \bigcup \{1\}$ 。
因此 $f(n)$ 就是第 $n+1$ 个没柱子可选的数$ -1=((n+1)^2-g(n+1)-1)-1$,化简得 $\lfloor \frac{n^2+1}{2} \rfloor+n-1$ 。
求出 $f(n)$ 以后需要证明 $f(n)+1$ 是不可行的,注意到最大的 $n+1$ 个数两两无法得到完全平方数即可。