【题解】CF1355E Restorer Distance

wsyhb · 2021-07-05 18:12:47 · 题解

前言

本文的主要目的是证明以最终高度为自变量，最小代价为因变量的函数是下凸函数。

其他题解的证明没有考虑到可能产生的 X \le Y 和 X>Y 的交界（X 和 Y 是下文证明中的未知数）。在此基础上，大多数题解的证明比较含糊；不含糊的@马保国官方号的题解的证明是错的（它计算 C' 的第三行漏掉了 AN 这一项，得出了 C'<0 这个错误结论）。

同时也希望各位读者：如果发现了本文中出现的任何错误，请立即在评论区指出或私信笔者，笔者将尽快回复和修改。

题解

首先，一次操作三相当于一次操作一和一次操作二，不妨令 M=\min(M,A+R)。

那么，执行 X 次操作一和 Y 次操作二的最小代价为 (X-\min(X,Y))A+(Y-\min(X,Y))R+\min(X,Y) \cdot M。
(即：将操作一和操作二尽可能配对，每对花费 M 的代价)

然后，设最终所有砖块的高度都变为了 H，那么上述的 X,Y 应满足 X=\sum_{h_i \le H}(H-h_i)，Y=\sum_{h_i>H}(h_i-H)。
（我们显然不会对同一砖块的高度又加又减）

设 f(H) 表示最终所有砖块的高度都变为了 H 的最小代价，则有：

(就是将第二段那个式子中的 \min(X,Y) 用 X 或 Y 代替）

为了方便，下文用 f(H) 相关的变量加上一撇表示 f(H+1) 相对应的变量。

设初始高度 \le H 的砖块恰有 P 个，则 X'=X+P，Y'=Y-(N-P)。

说一下 X',Y' 的计算方法：先将 X,Y 式子中的 H 变为 H+1，然后将 h_i=H+1 的部分从 Y 移到 X，就变成了 X',Y'。（其中 h_i=H+1 的部分在 X 和 Y 中都为 0，无影响)

令函数 f'(H)=f(H+1)-f(H)，分类讨论 f'(H) 的值：

若 X \le Y 且 X' \le Y'，则

若 X \le Y 且 X'>Y'，则

若 X>Y 且 X'>Y'，则

请注意：随着 H 的增大，X 增大，Y 减小，P 增大，(1)(2)(3) 三种情况依次出现。

由于 (1)(2)(3) 中除 P 以外都是定值，所以 f' 函数在 (1)(2)(3) 这三段分别单调不降。

(2)-(1) 得 M \Delta P+(X-Y+N)(A+R-M)。由于 \Delta P \ge 0，X-Y+N=X'+Y'+2(N-P)>0 且 M \le A+R，所以 (2)-(1) \ge 0，所以 (1)(2) 合起来也单调不降。

(3)-(2) 得 M \Delta P-(X-Y)(A+R-M)。由于 \Delta P \ge 0，X \le Y，M \le A+R，所以 (3)-(2) \ge 0，所以 (2)(3) 合起来也单调不降。

综上所述，f' 在定义域内单调不降—— f 是下凸函数。

P.S.

学过导数的人都知道 f' 就是 f 的导函数（注意 f 自变量为整数），而下凸函数的一种等价定义是其导函数单调不降，或表述为其二阶导函数恒 \ge 0。

如果你没学过导数，可以将其简单地理解为函数 f 变化量呈上升趋势，画个图就可以知道这可以判定下凸函数。

代码