CCNU 2012.7.8 Problem G

Problem G
Description
　　话说蹦蹦跳跳的小兔纸很可爱吧。
　　假设有一只兔纸在零点，每次会往左或者往右跳，但是这只兔纸跳第i步，它的跳跃距离一定为i，请问该兔纸最少要跳几步才能跳到位置n。
Input
　　第一行输入一个数T，表示测试数据个数，对于每个测试数据，输入一个数n(-10^9<=n<=10^9)，表示跳跃的最终位置。
Output
　　对于每组测试数据，输出1个数，表示该兔纸要跳几次才能跳到位置n。
Sample Input
　　2
　　2
　　6
Sample Output
　　3
　　3
Hint：
　　对于第一组测试数据，第一次往右边跳1格，跳到1，第二次往左边跳2格，跳到-1，第三次往右边跳3格，跳到2，因此跳3次
　　第二组测试数据三次都往右边跳，跳到6.

题目

问题转化一下，描述的就是求Sum(1...k) - 2*Sum_sub(1...k) = n

仔细考虑一下 Sum_sub(1...k) 是可以遍历 1 to (k+1)*k/2

所以需要求的这样一个k,直接暴就行了

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
long long sum(long long n)
{
    return n*(n+1)/2;
}
int main()
{
    freopen("G.in","r",stdin);
    freopen("G.txt","w",stdout);
    long long n;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&n);
        if(n<0)
            n*=-1;
        long long ans=0;
        for(;;ans++)
        {
            if(sum(ans)>=n&&(sum(ans)-n)%2==0)
            {
                printf("%lld\n",ans);
                break;
            }
        }
    }
    return 0;
}

View Code

G.in

G.out