CF505E Mr. Kitayuta vs. Bamboos
题意:有
之后的
然后,所有的竹子又会生长
你的目标是使
首先二分答案
对于一种方案,从最后一天开始倒着考虑,可以视为:每一天竹子各自缩短
易知,最后一天竹子越长,限制越少(任何一种可行方案,任意一棵竹子最后一天的长度增加,仍然合法)。
我们只需令所有的竹子结尾时都为
对每个竹子计算出需要多少天就会
然而我们的目标并不仅仅只是让所有的竹子不入土,还得保证结束时有一定高度
若某棵竹子操作后已经能预知在结束时达标,则不再考虑。这样就能优先操作那些可能不达标的。
注意在初始加入时也需要判断。
这可以使用堆来维护,若最后堆为空,则表示所有竹子都能达标。
复杂度