NOIP 2016系列解题报告 – [题组/NOIP]

Day2 T2 蚯蚓

你可以点击这个链接下载全部的AC代码

题目传送门(LOJ)

题解 :

如果按时间模拟的话,由于 m 很大,每次只能 O(1) 查最长并剪断。

考虑暴力的话,这显然是一个堆的形式,我们只要在堆外维护一个增加长度 val,对于拿出来剪断的两个蚯蚓,只要给它们的长度分别减 q 就可以了,对于某只蚯蚓,它的实际长度是 a[i]+val

用堆的话,每次是 \log m 级别的复杂度,m\log m 当然是过不了这道题的。 所以我们需要挖掘一些性质。

若最开始被排序好, 蚯蚓 i 的长度要长于 j 的话,那么设 i 被剪断成 i’_1, i’_2 j 被剪断成 j’_1,j’_2 则接下来的过程中 i’_1 一定会比 j’_1先剪断。

有了上面这个性质,我们可以维护三个队列,而且分别都是具有单调性的。

q1 维护从来没被剪断过的蚯蚓长度

q2 维护所有 \lfloor px\rfloor 的长度

q3 维护所有 x-\lfloor px\rfloor

这样维护,每次对比三个队首,取一个最长的拿来切,然后扔进 q1、q2 里。做 m 次就好啦

请注意各种特判带来的常数影响。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注