CSPS2023 T4 种树
__ryp__
·
·
个人记录
不算难。难点在于 CCF 独有的鹅心大分桃。
答案的单调性是显然的：第 x 天能完成，x + 1 天也定能完成，于是二分一个 m 作为答案，并转化为判定问题。
每棵树每天的增量是不小于一的，但是正由于这个一的下界，我们需要一个有点恶心的分桃。
忽略角标，我们设 g(x) 表示从 1 开始种，种到 x 时刻的总高度，设 z = \max \{0, \lceil\dfrac{1-b}c\rceil\} 是使得增量为一的点，定义域非负。
当 x \lt z 时显然有 g(x)= bx + \dfrac 1 2 cx(x + 1)；
当 x \ge z 时：
-
c\gt 0$，$g(x) = z + b(x - z) + \dfrac 1 2cx(x+1)-\dfrac 1 2 cz(z + 1)
-
c = 0$，$g(x) = bx
-
c \lt 0$，$g(x) = bz + \dfrac 1 2 cz(z + 1)+(x-z+1)
很难说这种傻逼线性柿子有什么意义，但凡换成随便其它一个不需要分桃的单调函数都行。但是出了就得做。。
找到所有的 $t$ 后，问题就转化为了：对每个点，我们为其分配一个 $x$ 使得 $1\le x \le t$ 且 $x_{\text{fa}_i}\lt x_i$，且 $x$ 不重。
那么我们按照 $t$ 排序，优先满足 $t$ 小的即可。
复杂度是两支 $\log$ 的，对应两个二分。