算步数-数学题

Description

给你坐标轴上的两个点A和B，请问从A走到B最少需要多少步？

我们对走的每一步的步长作出如下限制：

第一步和最后一步的步长必须是1，其他的任意一步的步长必须比前一步的步长小1、大1或相等。

Input

输入包含多组测试数据。每组输入两个整数A和B（0<=A<=B<2^31）。

Output

对于每组输入，输出从A走到B最少需要多少步。

Sample Input

45 48
45 49
45 50      

Sample Output

3
3
4      

解题思路

首先我感觉题意不明， 这道题实际上是每一步的步长必须比前一步的步长小1、大1或相等（包括第一步和最后一步），例如

1 8

如果按照我的想法应该是4步，步数分别是 1 2 3 1

然而实际上是 1 2 2 1 1

也就是说，由倒数第二个格子 跳到倒数第一个格子的时候也必须满足比前一步的步长小1、大1或相等

那么 肯定选择使得到达倒数第二个格子的步数越大越好，所以一定是2步 ，在前推一个格子一定是3………………

也就是说 这个步数应该满足这样一个数列：1 2 3 4 …n-1  n  n-1 ……4 3 2 1 = n^2

那么我们希望找到最大的n，尽可能使得上述的数列和 = 需要走的步数

于是我们找到第一个 不大于step的 n*n

得到上述数列的步数。

还剩step-n*n个格子没走，我们希望以最少的步数走完。也就是说尽量以每次走n个格子走完剩下的格子，即 left / n

由于可能不满足整除关系，但是剩余的格子数一定小于n，那么我们在 1 步之内一定能走完

代码

#include<cstdio>
using namespace std;
int main()
{
	long int a, b;
	while (scanf("%ld%ld", &a, &b) != EOF){
        long int step = b-a;
        if(step == 0) {puts("0");continue;}
        long int n = 0;

        while (n*n <= step) {n++;}
        n--;
        long int left  = step - n*n;
        long int add1 = left / n;
        long int add2  = left % n;
        long int ans = 2*n-1+add1;

        if(add2) ans += 1;

        printf("%ld\n",ans);

	}
}