蚂蚱跳跃问题-ag真人游戏

题目大意：
一个蚂蚱最初位于坐标轴的原点，现在蚂蚱要跳跃到坐标轴的s点，跳跃规则是蚂蚱既可以往正方向跳跃，也可以往负方向跳跃，蚂蚱第一次跳跃1个单位，以后的跳跃步数在前一步的基础上加一。现在求蚂蚱跳跃到s点最少需要多少步数？
原题截图如下：

题意分析：

首先看题目的数据最大约为10亿，意味着不可能采用搜索、暴力等一些耗时的解决办法，也不会让你在代码中开辟较大的数组，那么拿到这个问题如何去解决呢？

初步分析

1. 假如s为负，则只需求正s的结果

2. 如果目标点s恰好能等于s = f(n) =（n(n 1)）/2 , 说明最少只要经过n步就可以准确到达s点

3. s一定介于f(n)与f(n 1)之间，即 f(n) <= s <= f(n 1)

进一步分析 ：

1. 问题其实就是求一个序列1，2，3，…… , m-1, m的和要为s，其中这些数可正可负

2. 既然s = 1(-1) 2(-2) … … m(-m)那么蚂蚱必须至少要经过n步（因为f(n) <= s）才能使得步数之和为s

3. 假如所蚂蚱经过n步到达f(n)点，那么它下一步跳跃n 1个单位到达f(n 1)点，记 d = f(n 1) - s，

   如果d为偶数，那么一定存在一个数（1=< k <= n）使得 2*k = d , 也就是说 s = 1 2 ….. n (n 1)-d

   即s = 1 2 … (-k) …. n (n 1)，从而可以知道只要再走一步就可以实现1—n 1个不同符号的数相加和为s.

   假如 d为奇数，那么在1到n之间不可能有一个数的倍数为d，那么可以再走一步得f(n 2）- s =

   d2，如果d2为偶数，就得解，，否则就再走一步f(n 3) - s = t3,

   t2和t3一定有一个数为偶数，，问题就得解了,所以当d为奇数的时候要么再n的基础上再走两步，要么再走三步

具体代码实现如下：

/**得到第t步的位置**/
long result(int t){
    return (t*(t 1))/2;
}
/**得到位置x的临近点步数**/
getpos(long x) {
    int t = floor(sqrt(2*x));
    int r = t   2;
    while(t < r){
        if(result(t) > x){
            return t -1;
        }
        if(result(t) == x){
            return t;
        }
        t  ;    
    }
    return 0;
}
/**求解到达x的最少步数**/
int solve(int x){
    x = abs(x);
    int left = getpos(x);
    int leftresult = result(left);
    if(leftresult == x) return left;
    if((leftresult left 1-x)%2 == 1){
        return (left   2)%2 == 1 ? left   2 : left   3;
    }else{
        return left   1;
    }
}

虽然测试用例都通过，但是还是不知道能不能ac啊，昨天笔试时间短，竟然都没想出什么解法。。。