2022“杭电杯”中国大学生算法设计超级联赛(4)题解
本场比赛写出一个 1007
也写一篇题解吧!
1007
题目描述
![](/2022/07/28/2022%E2%80%9C%E6%9D%AD%E7%94%B5%E6%9D%AF%E2%80%9D%E4%B8%AD%E5%9B%BD%E5%A4%A7%E5%AD%A6%E7%94%9F%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E8%B6%85%E7%BA%A7%E8%81%94%E8%B5%9B%EF%BC%884%EF%BC%89%E9%A2%98%E8%A7%A3/1.png)
题目分析
就是给你 $n$ 层楼,每层楼有一个怪物,杀了怪物需要自己的攻击力超过它的血量,否则不能到达该楼层,一次可以跳 $k$ 以内的层或者下降一层,杀了怪物后这一层不能继续呆了,杀了怪物之后怪物的血量会成为自己的攻击力。
看标程是线段树写的,咱也不会,只能纯模拟啦。
首先可以肯定的一点就是:你跳了之后要把下面的怪物都收拾完,因为题目问你的是:能否解决所有怪物!!而你一次只能下降一层,不能去已经没有怪物的楼层。因此我们主要关注,我们要跳到哪里去,能收拾完下面的怪物。首先可以肯定的是:直接选择能跳的跳是肯定不行的,随便出一组数据便可知。
1 | 1 |
当你贪心地跳到第 $2$ 层之后你就会发现 $6$ 你收拾不了了。而这个数据是有解的,我们跳到第五层从上往下收拾完是能打过 $6$ 的。
那么其实我们就需要判断:我们跳了一个楼层之后是否能收拾下面的怪物,收拾下面的怪物是从上往下收拾,我们还可以沿途吃掉中间的怪物增长攻击力,但是这样的 check
乍一听好像是 O(n)
啊,不可行!但是其实我们可以把打不过的怪物堆起来,打得过的怪物直接扔掉,如果这次选择这层楼打不掉,那么我们选择更高的楼层去打。这样在整体的判断中,每个怪物只会被判一次,总时间复杂度能接受。
具体实现方式我们可以用栈,首先如果当前楼层我能打过我肯定直接打了,因为上一层比不上一层打肯定要好的,上了一层我还能多一个选择。那么如果当前打不过,我们就先压栈,循环k以内的数据,如果能打过,尝试过来打,并开始从栈中取出怪物来看看能否打过,能打过扔出来,打不过则继续往上走。那么不难发现,我们如果跳到了 $p$ 层,要判断能否结局 $p-i$ 层的怪物我们只需要把当前攻击力加上 $p-i+1——p$ 的怪物数值之和能否超过它的血量即可。那么这里算到和的话我们就可以前缀处理了。那么为什么不需要重复判断呢?因为我跳到这一层时,我都能打过这个怪物了,我跳到更高的层来打这个怪物会打不过?
如果说 $k$ 层遍历完了之后,我栈里面还有数据,说明我跳哪都打不完这些怪物,就放弃了。如果能跳 $p$ 层打过,我当前在 $q$ 层的话,那么我在解决完之后我身处 $q+1$ 层,中间 $q+1——p$ 层都是空楼层,都不能去,因此我们把自己放到 $p$ 层,但是同时可选择的范围要随着之前跳的高度减少。因为我原来在 $q+1$ 层本来也就只能跳到 $q+k$ 层嘛,这个应该很好理解。
那么看完这些之后,相信你不难理解下面的标程了。
标程
1 |
|