算步數-數學題

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);

	}
}