UVa 846 步数

/*

* 解题思路：

* 这题就是找规律题：

* 由下找规律知序号1 -> 1

*                                      4 -> 1 2 1

*                                      9 -> 1 2 3 2 1

*                                    16 -> 1 2 3 4 3 2 1

*                                          ..........( 每行数位差2!! )

*         可以看出规律来吧,最中间那个数是前面序号的开方,然后根据观察可以发现，

*

*         在序号4~9间，共有5个数，前面两个4位，后面3个5位

*          在序号9~16间，共有7个数，前面三个6位，后面4个7位

*

*          可以推出规律：假设一个区间里有n个数字 ，前 n / 2个数为一种数位，n-n/2个数为后一种数位，

*          刚好为1,4,9,16...这样的数位为( sqrt( 序号 )*2 -1 )（等差数列）个数位,

*/

1:  1
2   1 1
3   1 1 1
4:  1 2 1 
5   1 2 1 1
6   1 2 2 1
7   1 2 2 1 1
8   1 2 2 2 1
9:  1 2 3 2 1
10  1 2 3 2 1 1
11  1 2 3 2 2 1
12  1 2 3 3 2 1
13  1 2 3 3 2 1 1
14  1 2 3 3 2 2 1
15  1 2 3 3 3 2 1
16: 1 2 3 4 3 2 1

#include <math.h>
#include <stdio.h>
int main( )
{
    int t,x,y,num,tmp,m,n;

    scanf("%d",&t);
    while( t-- )
    {
        scanf("%d%d",&x,&y );
        num = y-x;
        if( !num )
            printf("0\n");
        else
        {
            tmp = sqrt( num );
            n = pow(tmp , 2 );
            m = ( pow( tmp+1 , 2 )-pow(tmp , 2 ) )/2;
    
            if( num-n > m )
                printf("%d\n",2*( tmp+1 )-1 );
            else if( num-n == 0  )
                printf("%d\n",2*tmp-1);
            else
                printf("%d\n",2*tmp);
        }
    }
    return 0;
}

UVa 846 步数

原文：http://blog.csdn.net/u011886588/article/details/19168569