前言
在 NOI2016D1T2 国王饮水记中有一个叫定理 10 的东西，picks 讲课的 PPT 中并没有给出详细的推导过程。本人根据 PPT 中所说的大致思想，尝试证明了定理 10，现写在下方。如有错误或不严谨之处，麻烦指出，万分感激。
证明
假设我们的最优解有 l 段长度大于 1，这些段的长度记为 $L_i(i∈[1，l])$, 每段水位的平均值记为 $a_i$, 我们考虑每一个城市的水位的贡献, 用这些贡献拼出最后的高度。
最优解的最终高度：
$$
\frac{\frac{\frac{\frac{\frac{x+L_{1}a_{1}}{L_{1}+1}+L_{2}a_{2}}{L_{2}+1}…+L_{l}a_{l}}{L_{l}+1}+h_{1}}{2}+h_{2}}{2}….
$$
按照 PPT 所说替换之后的最终高度：
$$
\frac{\frac{\frac{\frac{x+L_{2}a_{2}}{L_{2}+1}…+L_{l}a_{l}-a_{l+1}}{L_{l}}+a_{l+1}}{2}+h_{1}}{2}….
$$
根据我们的假设，上式大于等于下式。因为显然对于后面若干个长度为一的操作区间，对于答案的贡献是一样的，所以我们要比较的实际上就是：
$$\frac{\frac{\frac{x+L_{1}a_{1}}{L_{1}+1}+L_{2}a_{2}}{L_{2}+1}…+L_{l}a_{l}}{L_{l}+1}
$$
和：
$$
\frac{\frac{\frac{x+L_{2}a_{2}}{L_{2}+1}…+L_{l}a_{l}-a_{l+1}}{L_{l}}+a_{l+1}}{2}
$$
写成和式的形式：
$$
\frac{x}{\Pi_{i=1}^{l}(L_{i}+1)}+\sum_{i=1}^{l}\frac{L_{i}a_{i}}{\Pi_{j=i}^{j<=l}{(L_{j}+1})}
$$
$$
(L_{1}+1)\frac{x}{\Pi_{i=1}^{l}(L_{i}+1)\frac{2L_{l}}{L_{l}+1}}+\sum_{i=1}^{l}\frac{L_{i}a_{i}}{\Pi_{j=i}^{j<=l}(L_{j}+1)\frac{2L_{l}}{L_{l}+1}}+a_{l+1}\frac{L_{l}-1}{2L_{l}}
$$
由上式>下式得：(下面是移项并整理的结果)
$$
\frac{L_{1}a_{1}}{\Pi_{i=1}^{l}(L_{i}+1)}\geq(\frac{(L_{l}+1)(L_{1}+1)}{2L_{l}}-1)\frac{x}{\Pi_{i=1}^{l}(L_{i}+1)}+\frac{1-L_{l}}{2L_{l}}\sum_{i=1}^{l}\frac{L_{i}a_{i}}{\Pi_{j=i}^{j<=l}{(L_{j}+1})}+a_{l+1}\frac{L_{l}-1}{2L_{l}}
$$
最前面一项不好处理，直接甩掉。（当然最前面一项大于 0，可以轻松地证明，这里不赘述）
$$
\frac{L_{1}a_{1}}{\Pi_{i=1}^{l}(L_{i}+1)}\geq\frac{1-L_{l}}{2L_{l}}\sum_{i=1}^{l}\frac{L_{i}a_{i}}{\Pi_{j=i}^{j<=l}{(L_{j}+1})}+a_{l+1}\frac{L_{l}-1}{2L_{l}}
$$
$$
\frac{L_{1}a_{1}}{\Pi_{i=1}^{l}(L_{i}+1)}\geq\frac{L_{l}-1}{2L_{l}}(a_{l}-\sum_{i=1}^{l}\frac{L_{i}a_{i}}{\Pi_{j=i}^{j<=l}{(L_{j}+1})})
$$
把 $a_{l}$放缩成 $a_{l-1}+\Delta$, 拿出 $a_{l-1}$这一项，整理化简:
$$
\frac{L_{1}a_{1}}{\Pi_{i=1}^{l}(L_{i}+1)}\geq\frac{L_{l}-1}{2L_{l}}(\frac{1}{L_{l}+1}a_{l}-\sum_{i=1}^{l-1}\frac{L_{i}a_{i}}{\Pi_{j=i}^{j<=l}{(L_{j}+1})})+\frac{L_{l}-1}{2L_{l}}\Delta
$$
继续放缩，拿，一直拿完所有的，化简可得：
$$
\frac{L_{1}a_{1}}{\Pi_{i=1}^{l}(L_{i}+1)}\geq\frac{L_{l}-1}{2L_{l}}(\frac{a_{1}}{\Pi_{i=1}^{l}{(L_{i}+1})})+\frac{L_{l}-1}{2L_{l}}\Delta
$$
甩掉第一项（影响不大）：
$$
\frac{L_{1}a_{1}}{\Pi_{i=1}^{l}(L_{i}+1)}\geq\frac{L_{l}-1}{2L_{l}}\Delta
$$
这个和 PPT 里面只是一个 $log_{3}2$的差距（约等于 0.64）。
从这个式子推到卡住 $l$的界的过程很简单，注意任何一个 L 大于等于 2 即可，在此不赘述。
以上。
结语
我为什么在一个无聊的化简上浪费了 2 个月啊！！！
写完之后才发现这个定理的证明其实并不重要，这个定理几乎全部的意义在于它通过微调最优解来卡某个值的界的这种毒瘤的想法，真的 nb。
这应该是我留在 OI 界的最后一篇算是有一点点意义的博文了，仅以此纪念我早已退役的 OI 生涯。
0 条评论