第二十五题:

2590:Steps

题目链接：

P2590——Steps——柒行（www.oj7.cn）

题目来源：

Waterloo local 2000.01.29

题目描述

总时间限制:

1000ms

内存限制:

65536kB

描述

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 consists of a line containing n, the number of test cases.

输出

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.

样例输入

3
45 48
45 49
45 50

样例输出

3
3
4

中文题面：

描述

一步走过直线上的整数点。每一步的长度必须是非负的，并且可以比前一步的长度大$1$、等于前一步的长度或小$1$。 从x走到y所需的最少步数是多少？第一步和最后一步的长度必须是$1$。 输入 输入包含一行，其中包含$n$，即测试用例的数量。 输出 对于每个测试用例，后面会跟着一行，包含两个整数：$0 <= x <= y < 2*31$。对于每个测试用例，打印一行，给出从x到y所需的最少步数。

输入

输入包含一行，其中包含一个整数 $n$，表示测试用例的数量。

输出

对于每个测试用例，接下来有一行包含两个整数 $x$ 和 $y$（满足 $0≤x≤y<2*31$）。对于每个测试用例，输出一行，给出从 $x$ 到 $y$ 所需的最小步骤数。 样例输入

3
45 48
45 49
45 50

样例输出

3
3
4

算法标签

贪心算法

解题思路：

读取测试用例的数量以及每个测试用例的起始点 $x$ 和终点 $y$。计算从 $x$ 到 $y$ 的距离 $d=y−x$。

情况一：

步数k为奇数$（k=2n-1）$ 步长序列结构：$1,2,3,...,n-1,n,n-1,...,2,1$ 总步数：序列长度为 $2n-1$（例如 $n=3$ 时，序列为 $1,2,3,2,1$，共 $5$ 步）。 能走的最大步数为：$n²$

情况二：

步数k为偶数$（k=2n）$ 步长序列结构：$1,2,3,...,n,n,n-1,...,2,1$ 总步数：序列长度为 $2n$（例如 $n=3$ 时，序列为 $1,2,3,3,2,1$，共 $6$步）。 能走的最大步数为$n(n+1)$

确定范围： 通过奇偶步数的交替，可以覆盖连续的区间：

当 $k=2n-1$ 时，覆盖范围 $[ (n-1)² + 1, n² ]$。

当 $k=2n$ 时，覆盖范围 $[ n² + 1, n(n+1) ]$。

当 $k=2n+1$ 时，覆盖范围 $[ n(n+1) + 1, (n+1)² ]$。

根据 $d$ 与 $n$ 的关系判断步数：

如果 $d>n∗(n+1)$，输出 $2∗n+1$。

如果 $d>n∗n$，输出 $2∗n$。

否则，输出 $2∗n−1$。

实现步骤：

读取输入：

读取测试用例数量 $n$。

判断条件输出结果

每个测试用例： 读取每个测试用例的起始点 $x$ 和终点 $y$。 计算距离 $d=y−x$。 计算平方根 $n=sqrt(d)$。 根据 $d$ 与 $n$ 的关系判断步数： 如果 $d>n∗(n+1)$，输出 $2∗n+1$。 如果 $d>n∗n$，输出 $2∗n$。 否则，输出 $2∗n−1$。

C++实现：

#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++){
        int x,y;
        cin>>x>>y;
        int d=y-x;
        if(d==0){
            printf("0\n");
            continue;
        }
        int n=(int)sqrt(d);
        if(d>n*(n+1)){
            printf("%d\n",2*n+1);
        }else if(d>n*n){
            printf("%d\n",2*n);
        }else{
            printf("%d\n",2*n-1);
        }
    }
    return 0;
}