关注我，分享高质量每日一题题解~

b站同名账号分享力扣杯历届真题视频题解，也欢迎大家提出宝贵意见！

思路：贪心

• 由于兔子可以跳到非整数坐标的点上，所以若存在数组中某个元素 $a[i]$ 大于当前剩余距离 $d$ ，则必可以通过两次对称的斜向跳跃覆盖完剩余距离。所以我们需要对数组进行排序，即可得到数组最大的元素。如果存在某个元素等于当前剩余距离，则只需要一次横向跳跃即可到达。所以需要利用哈希表记录是否存在与当前剩余距离 $d$ 相等的数组元素。
• 当 $a[n - 1] >x$ 时，我们只需要判断是否存在与 $x$ 相等的元素即可，若存在则只需要 $1$ 次跳跃，若不存在则需要 $2$ 次跳跃。若 $a[n - 1] = x$，当然只需要 $1$ 次跳跃即可。
• 当 $a[n - 1] < x$ 时，我们至少需要 $2$ 次跳跃才可以到达终点（因为一次最多跳 $a[n - 1]$）。我们不妨设每次跳跃均使用最长可跳跃距离 $a[n - 1]$，那么经过 $\lceil \frac{x}{a[n-1]} \rceil$ 次横向跳跃后，我们覆盖的距离 $dist$ 一定在 $[x, x + a[n - 1])$ 范围内，那么我们必可以从跳跃次数中选取出 $2$ 次跳跃，使这两次跳跃变为对称的斜向跳跃，以抵消覆盖距离大于 $x$ 的部分。所以结果即为 $\lceil \frac{x}{a[n-1]} \rceil$ 。

代码（C++）

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

int main() {
    int T = 1;
    cin >> T;
    while(T--) {
        int n, x;
        cin >> n >> x;
        vector<int> a(n);
        map<int, int> mp;
        for(int i =0 ; i < n; i++) {
            cin >> a[i];
            mp[a[i]] = 1;
        }
        sort(a.begin(), a.end());

        int ret = 0;

        if(x < a[n - 1]) {
            if(mp[x]) ret = 1;
            else ret = 2;
        } else {
            ret = (x + a[n - 1] - 1) / a[n - 1];
        }


        cout << ret << endl;
    }
    return 0;
}

时间复杂度：$O(nlgn)$