TC-SRM-587-div1-250

2016.10.11 16:23 Tue | 220次阅读 | ioi2017集训队作业 | 固定链接 | 源码

250 JumpFurther

作者:jkxing
关键词:特判

题目描述

你有n次走台阶的机会,第i次,你要么不走,要么走i阶(直接跨上去,不踩中间的),现在,有一级坏了的台阶,你不能踩在坏的台阶上,问n次后最高能上到哪里。

时间、空间限制

2s/64MB

数据范围

$n\le 2000$

分析

没有坏的台阶,答案自然是$n*(n+1)/2$
如果有坏的台阶m,并且对答案有影响,那m一定可以表示成$i*(i+1)/2$,其中i是一个小于等于n的正整数。
于是只要不走第一步,就一定不会经过x。
所以答案要么是$n*(n+1)/2$,要么是$n*(n+1)/2-1$。

算法

只要枚举1到n看是否有$i*(i+1)/2=m$就可以了。

时空复杂度

时间复杂度$O(n)$
空间复杂度$O(1)$