一個人沿著一數線前進。他每次走的長度（整數）必須是正的，而且比上一步走的長度多1，一樣，或少1。另外請注意：第一步及最後一步的長度一定是1.
請問這個人若要從x走到y，最少需要走幾步。
舉例說明：若x=45, y=50，那麼每步走的長度可以是：1,2,1,1，所以最少需要4步。
Input
輸入的第一列有一個正整數代表以下有幾組測試資料。每組測試資料一列，含有2個整數x,y（0 <= x <= y < 231）。
Output
每組測試資料輸出一列，最少需要走幾步才能從x走到y。
Sample Input
3
45 48
45 49
45 50
Sample Output
3
3
4
找出步數與距離的關係即可得解。
- 0步最多能抵達的距離是0
- 1步最多能抵達的距離是1(1)
- 2步最多能抵達的距離是2(1 1)
- 3步最多能抵達的距離是4(1 2 1)
- 4步最多能抵達的距離是6(1 2 2 1)
- 5步最多能抵達的距離是9(1 2 3 2 1)
- 6步最多能抵達的距離是12(1 2 3 3 2 1)
- ……以此類推
题意：在给出的两个数A，B，找出最少需要几步可以从A到B，规则：第一步和最后一步必须是1，还有中途只可以比前一数大一，等于，或小一。。
第一种方法：从A，B开始依次加，然后距离减去步长，直到 dis<0 ，我们可以肯定的是，小于零的这部分C，一定小于当前的步长N，所以我们一定能在之前的步长中找到(N-C)，也就可以填满这一部分。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int n;
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int a,b;
scanf("%d%d",&a,&b);
int dis = b - a ;
bool flag = false ;
int count = 0 ;
int step = 1 ;
while (dis > 0 )
{
dis -= step;
count++;
if (flag)
step++;
flag = !flag;
}
printf("%d\n",count);
}
return 0;
第二种方法：1+2+…..+(n-1)+n+(n-1)+….2+1 =n^2，这是我们在达到和为n^2在满足题意的情况下能确定的最少步数，设想我们如果 dis==n^2 ,那结果就显而易见了，当dis > n^2的时候，首先我们先确定最大的n满足 n^2 <= dis ,然后我们只要再找dis-n^2的数就可以，如果dis-n^2<=n，那只要再找一个,如果>n,但我们发现这个数一定<(n+1）^2-n^2
,那这个数一定可以化为数列中的两个数。。。
/*
Author:ZCC;
Solve:
// 所走步数对应的序列如果左右对称，那么所走的步数应该是最少的。因为最先一步和最后一步长度均必须是
// 1，又由于每一步的长度必须是非负整数，且要么比上一步步长恰好大 1，要么相等，要么小 1，则左右对
// 称的序列能在最少步数得到最大距离。如果采取左右对称的走法，设两点距离为 distance，n = sqrt
// （distance），则由于最大步数为 n 步时能达到的距离是 1 + 2 + 3 + ... + （n - 1） + n +
// （n - 1） + ... + 3 + 2 + 1 = n^2。比较两点距离 distance 与 n^2，若相等，表明只需走
// 2 * （n - 1） + 1 = 2 * n - 1 步，否则若剩余距离 distance - n^2 在 1 - （n + 1），
// 只需插入一步即可，若 distance - n^2 大于 （n + 1），则需多插入两步即可。
*/
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
int t ;
scanf("%d",&t);
while (t--)
{
int a,b;
scanf("%d%d",&a,&b);
int dis = b - a ;
if (dis <= 3)
printf("%d\n",dis);
else
{
int n = sqrt(dis);
if ( n * n == dis)
printf("%d\n",2*n-1);
else if ((dis-n*n)<=n)
printf("%d\n",2*n);
else printf("%d\n",2*n+1);
}
}
return 0;
}
列出几项，找到规律：
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
可以得出 n * n : 2 * n – 1
综合得出：
n * n： 1……n……1 minstep: 2 * n – 1.
n * ( n + 1 ） 1…..n,n…….1 minstep: 2 * n
（n + 1) * ( n + 1 ) :1……n+1………1 minstep: 2 * n + 1
代码：
#include <stdio.h>
#include <math.h>
int main()
{
int ncase;
scanf("%d", &ncase);
while (ncase--)
{
int x, y;
scanf("%d%d", &x, &y);
x = y - x;
if (x == 0)//debug
printf("0\n");
else
{
y = (int)sqrt(x);
if (x == y * y)
{
printf("%d\n", 2 * y - 1);
}
else if (x <= y * (y + 1))
{
printf("%d\n", 2 * y);
}
else
{
printf("%d\n", 2 * y + 1);
}
}
}
return 0;
}
