UOJ Logo kczno1的博客

博客

「网络流 24 题」魔术球 贪心的正确性证明

2018-10-17 08:25:11 By kczno1

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

评论

Saigetsu
%%%(您可以去做机器人路径规划了)
OldDriverTree
您什么时候证明您第六分块的做法的复杂度啊
TLE
%%%
TLE
@kczno1 您太强了
Leoleepaytser
@kczno1 太强了orz

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。