一个蚂蚱是怎么跳的最初位于坐標轴的原点现在蚂蚱是怎么跳的要跳跃到坐标轴的s点,跳跃规则是蚂蚱是怎么跳的既可以往正方向跳跃也可以往负方向跳跃,蚂蚱是怎么跳的第一次跳跃1个单位以后的跳跃步数在前一步的基础上加一。现在求蚂蚱是怎么跳的跳跃到s点最少需要多少步数
首先看题目的數据最大约为10亿,意味着不可能采用搜索、暴力等一些耗时的解决办法也不会让你在代码中开辟较大的数组,那么拿到这个问题如何去解决呢
-
假如S为负,则只需求正S的结果
-
如果目标点S恰好能等于S = F(n) =(n(n+1))/2 , 说明最少只要经过n步就可以准确到达S点
-
问题其实就昰求一个序列12,3…… , m-1, m的和要为S,其中这些数可正可负
-
假如 d为奇数那么在1到n之间不可能有一个数的倍数为d,那么可以再走一步得F(n+2)- S =
t2和t3┅定有一个数为偶数,问题就得解了,所以当d为奇数的时候要么再n的基础上再走两步要么再走三步
虽然测试用例都通过,但是还是不知道能不能AC啊昨天笔试时间短,竟然都没想出什么解法。