【OJ】小兔蹦蹦跳Ⅰ

谁借莪１个温暖的怀抱￠ 2023-10-09 11:35 9阅读 0赞

## 1710: 小兔蹦蹦跳Ⅰ ##

### 题目描述 ###

小兔位于X轴的x点，欲跳至X轴的y点。x，y均为整数。小兔每次沿x轴直线跳跃，每跳的长度均为正整数，假设

小兔一共跳了n次才到目的地，每次跳的长度为F1，F2，…, Fn. 有规则如下：  
F1=Fn=1  
 ∣ F i − F i − 1 ∣ < = 1 |F\{i\}-F\_\{i-1\}|<=1 ∣Fi−Fi−1∣<=1 ， 2<=i<=n (注：| |是绝对值符号）  
我们的问题是给定x，y， 如何使得n最小。

### 输入 ###

包含多组数据，但不超过1000组。每组数据一行，每行包括两个整数x和y。0 <= x < y <= 1000000000 。

### 输出 ###

对于每一组数据，输出一行，即从x到y的最小跳跃次数n。

### 样例输入 ###

45 48
    45 49
    45 50

### 样例输出 ###

3
    3
    4

### 问题分析 ###

设输入的x与y的差值为calc，小兔需要跳的步数为result，则对于这个题目的解答：

calc = 1 ----> result = 1	----> 1
    calc = 2 ----> result = 2   ----> 1 + 1
    calc = 3 ----> result = 3 	----> 1 + 1 + 1
    calc = 4 ----> result = 3   ----> 1 + 2 + 1
    calc = 5 ----> result = 4   ----> 1 + 2 + 1 + 1
    calc = 6 ----> result = 4   ----> 1 + 2 + 2 + 1
    calc = 7 ----> result = 5   ----> 1 + 2 + 2 + 1 + 1
    calc = 8 ----> result = 5   ----> 1 + 2 + 2 + 2 + 1
    calc = 9 ----> result = 5   ----> 1 + 2 + 3 + 2 + 1
    ....

现在研究对于 result步，最多能够走多远，记作max

result = 1 	max = 1
    result = 2  max = 2
    result = 3  max = 4    1 + 2 + 1
    result = 4  max = 6    1 + 2 + 2 + 1
    result = 5  max = 9    1 + 2 + 3 + 2 + 1
    result = 6  max = 12   1 + 2 + 3 + 3 + 2 + 1
    result = 7  max = 16   1 + 2 + 3 + 4 + 3 + 2 + 1
    ....

所以对于result 步，最多可以走max远，计算后公式如下：

max = ((result+1)*(result+1)-1)/4 	当result为偶数时
    max = ((result+1)*(result+1)/4)		当result为奇数时

接下来就是反过来，根据 calc —> max —> result

### 解题代码 ###

#include <stdio.h>
    #include <math.h>
    
    /** * 判断x是不是平方数 */
    bool sqrted(long long x)
    { 
        long long temp = sqrt(x);
        return temp*temp == x;
    }
    
    // written by Smileyan
    int main()
    { 
        long long m,n;
        while(scanf("%lld%lld",&m,&n)==2)
        { 
            long long calc = n - m;
            // 一直+1，指导它成为一个平方数
            while(sqrted(calc*4+1) != true && sqrted(calc)!=true)
            { 
                calc++;
            }
            long long result;
    
            // 简单计算
            if(sqrted(calc*4+1) == true)
                result = sqrt(calc*4+1)-1;
            else
                result = sqrt(calc*4)-1;
            printf("%lld\n",result);
        }
    
        return 0;
    }

### 总结 ###

研究规律+数学运算。

> Smileyan  
> 2019年9月25日 13:10