JumpFurther

作者：邢健开 徐明宽

关键词：特判

题目描述

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

时间、空间限制

2s/64MB

数据范围

$n\le 2000$，$m \le 4000000$

分析

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

算法一

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

时空复杂度

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

算法二

注意到满足$i*(i+1)/2=m​$的$i​$一定满足$i = \lfloor\sqrt{2m}\rfloor​$，于是只需检验这一个$i​$即可。

时空复杂度

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