题目描述

一只兔子位于二维平面的原点 (0,0) 处，它想通过一系列的跳跃，跳到点 (x,0) 处。

给定一个长度为 n 的数组 a1,a2,…,an。

兔子能从一个点跳到另一个点，当且仅当两点之间的距离等于上述数组中的某个元素的值。

请问，兔子从 (0,0) 到 (x,0) 最少需要跳几次？

注意，兔子可以跳到非整数坐标的点上。

例如，当 x=4，a={1,3} 时，(0,0)→(1,0)→(4,0) 和 (0,0)→(2,5√)→(4,0) 均为合理最佳方案之一。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含两个整数 n 和 x。

第二行包含 n 个整数 a1,a2,…,an。

输出格式
每组数据输出一行结果，表示最少跳跃次数。

数据范围
1≤T≤1000,
1≤n≤105,
1≤x≤109,
1≤ai≤109,ai 各不相同。
保证同一测试点内所有 n 的和不超过 105。

样例

输入样例：
4
2 4
1 3
3 12
3 4 5
1 5
5
2 10
15 4
输出样例：
2
3
1
2

算法1

(暴力枚举) $O(n^2)$

1.如果可以一步，则1步

2.如果有比x还大的步子，通过构成一个三角形，2步可以搞定

3.如果最长的步子比x小。就迈最大的步子

时间复杂度

参考文献

Python3 代码

T = int(input())
for _ in range(T):
    n, x = map(int, input().split())
    a = [int(x) for x in input().split()]

    if x in a:
        print(1)
    else:
        max_num = max(a)
        if max_num > x:
            print(2)
        else:
            res = 0
            if x % max_num == 0:
                res = x // max_num
            else:
                res = x // max_num + 1
            print(res)

c++代码

# include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;    cin >> T;
    while (T --)
    {
        int n;    cin >> n;
        int x;    cin >> x;
        vector<int> a (n);
        for (int i = 0; i < n; i ++)
            cin >> a[i];

        if (count(a.begin(), a.end(), x) > 0)
        {
            cout << 1 << endl;
        }
        else
        {
            int max_num = *max_element(a.begin(), a.end());
            if (max_num > x)
            {
                cout << 2 << endl;
            }
            else
            {
                if (x % max_num == 0)
                    cout << x / max_num << endl;
                else
                    cout << x / max_num + 1 << endl;
            }
        }
    }


    return 0;    
}

java代码

import java.util.* ;

public class Main
{
    public static void main (String [] args)
    {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T -- > 0)
        {
            int n = scan.nextInt();
            int x = scan.nextInt();

            int [] a = new int [n];
            for (int i = 0; i < n; i ++)
                a[i] = scan.nextInt();

            boolean find_x = false;
            for (int i = 0; i < n; i ++)
                if (a[i] == x)
                    find_x = true;
            if (find_x == true)
                System.out.println(1);

            else
            {
                int max_num = 0;
                for (int i = 0; i < n; i ++)
                    max_num = Math.max(max_num, a[i]);
                if (max_num > x)
                {
                    System.out.println(2);
                }
                else
                {
                    if (x % max_num == 0)
                    {
                        System.out.println(x / max_num);
                    }
                    else
                    {
                        System.out.println(x / max_num + 1);
                    }
                }
            }
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla