题解:P8767 [蓝桥杯 2021 国 A] 冰山

· · 题解

题意

告诉你冰山的生长方式,让你求出每一次冰山的大小之和。

做法

首先想到冰山的生长,如果我们不停的让 X_i10^9,那么冰山数量一下子就会超过 10^{18},然后炸掉,所以我们可以想到使用二元组去维护冰山,一个二元组 {(x,y)} 表示大小为 x 的冰山有 y 个,但是想到还是会炸,所以我们维护的时候就可以实时对 y 取模。\ 所以算法就比较清晰了,我们用一个 map 去维护这些二元组,然后记录一个 sum 表示 {(x,y)} 实际上是表示的 x+sum 的冰山有 y 个,那么我们每一次操作就可以分类讨论,如果 X \le -1,就只用从 map 的最左边一直弹出被融化掉的冰山,即满足 x+sum+X \le 0 的二元组,同理,如果 X \ge 1,那么就判断 x+sum+X 是否比 k 大,如果比 k 大,那么就自然要分裂了,注意每一次记得取模。

时间复杂度

首先一开始的 n 是少不了了,然后看每一次的冰川的分裂情况,如果 X 是负数,那么冰川的数量就会减少,相较于后面的处理时间复杂度就会相应地减少。如果 X 是正的,那么最坏情况就是分裂出来了 1,k,x+X 这三种冰川,依然是线性的,所以最后的时间复杂度就是 (n + m)\times \log_2n

代码

代码就不放了。