CF505E Mr. Kitayuta vs. Bamboos

题意:有 棵竹子,初始高度为 ,生长速度为

之后的 天,早上你可以选择 棵竹子,都砍掉 个单位长度,若 则变为 (但竹子不会死亡,仍然会生长)。

然后,所有的竹子又会生长 单位长度。

你的目标是使 天结束后最长的竹子最短。

,时限


首先二分答案

对于一种方案,从最后一天开始倒着考虑,可以视为:每一天竹子各自缩短 ,然后选择 棵竹子将其拔高 。需满足过程中所有的竹子长度都不能

易知,最后一天竹子越长,限制越少(任何一种可行方案,任意一棵竹子最后一天的长度增加,仍然合法)。

我们只需令所有的竹子结尾时都为 ,看看能否将其调整使得开始时


对每个竹子计算出需要多少天就会 ,给 比较近的竹子优先拔高。

然而我们的目标并不仅仅只是让所有的竹子不入土,还得保证结束时有一定高度

若某棵竹子操作后已经能预知在结束时达标,则不再考虑。这样就能优先操作那些可能不达标的。

注意在初始加入时也需要判断。

这可以使用堆来维护,若最后堆为空,则表示所有竹子都能达标。

复杂度