POJ-2590-Steps题目详解，思路分析及代码，规律题，重要的是找到规律~~

Steps

Time Limit: 1000MS		Memory Limit: 65536K

http://poj.org/problem?id=2590

Description

One steps through integer points of the straight line. The length of a step must be nonnegative and can be by one bigger than, equal to, or by one smaller than the length of the previous step.

What is the minimum number of steps in order to get from x to y? The length of the first and the last step must be 1.

Input

Input consists of a line containing n, the number of test cases.

Output

For each test case, a line follows with two integers: 0 <= x <= y < 2^31. For each test case, print a line giving the minimum number of steps to get from x to y.

Sample Input

Sample Output

Source

Waterloo local 2000.01.29

题目意思很好懂：求x点到y点的最小步数,起始和结束的都只能走一步，中间的可以等于前一步，可以比前一步大一或小一；

我们可以推算出，假设走n步，所能达到的最长距离为：1+2+3+4+...+(n+1)/2+...+4+3+2+1;明白了吧，1 2 3 4 5 ...(n+1)/2... 5 4 3 2 1 ;是不是很熟悉；；

步数(n)：最大距离 f(n)

1 1 f(1)=1;

2 1 + 1 f(2)=2=f(1)+(2+1)/2;

3 1 + 2 + 1 f(3)=4=f(2)+(3+1)/2;

... ... ...

n 1 + 2 + 3 +...+ (n+1)/2 +...+ 3 + 2 +1 f(n)=f(n-1)+(n+1)/2;

这样的话方法就多了，可以把距离与步数的关系打表，然后算出距离差，二分查找即可，但开始我有个疑问，如果这个差值介于f(n)与f(n-1)之间怎么办，我们知道n-1步所能达到的最大距离是f(n-1)，如果f(n-1)还比差值小，那么无论如何n-1步都是无法达到的，即只能在n步达到；

这里介绍一种很好的方法，代码简洁易懂，思路都差不多；

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

int find(int x)

{

    int i,a=1;

    for(i=2;;i++)

    {

        a+=(i+1)/2;//a为i步能达到的最大距离，这样连打表都不用了；

        if(a>=x)

            break;

    }

    return i;

}

int main()

{

    int t,a,b;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&a,&b);

        if(b-a<=3)

            printf("%d\n",b-a);//革除了a b 相等的情况；

        else

            printf("%d\n",find(b-a));

    }

    return 0;

}

巴特西

POJ-2590-Steps题目详解，思路分析及代码，规律题，重要的是找到规律~~

最新文章

热门文章