题目大意:
思路:
- 这题难点在于每一秒会恢复值而且(mi+ri,ci) 有一个阈值.
- 发现 一个点被清理后, 他的恢复有3个状态, 一次恢复 ri的值, 当 t<ci/ri, 恢复 ci%ri值 当t=[ci/ri ]+1(且是除不尽时) ,然后就时恢复 0, 当t>前面的时间
- 又发现 总共恢复的时间不会超过 2*10; 那么就预处理差分的差分求每一个块的值, 第二个差分是没秒恢复多少差值.
- 预处理时间是 n根号n; 刚好1s
- 在对每一块弄一个flag元素
- 对怪每一次处理块时,看 这个块是否被一次性杀了, 是 又看他的值能不能杀掉怪怪物,能就暴力处理, 不能就杀光,flag=1, 去下一个块
- 没有被一次性杀, 就暴力处理. 时间复杂度分析: 由于每一个怪物最多留下一个要我们暴力处理的块,(处理后会flag=1,或者暴力还是他) 所以这里会增加n根号n时间
- 总时间2 n根号n, 题目时间是4s, 不会超过
- 但是空间复杂度会超过, 怎么办呢?
- 考虑\,用当前块的时候,才预处理这个块. 这样空间为 n.
- 用块来作为外层循环, 怪物作为内存循环(离线查询)