我曾经在 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$ 个数两两无法得到完全平方数即可。