题目描述

在一个二维空间中，兔子从 (0,0) 到 (x,0) 最少需要跳几次？

本想用硬币组合的方法去求，观察下题意发现可以贪心。。

由于是在一个二维的空间中，无论用哪一种a[i]都可以实现的，就只用这一个a[i]去走就行！！

样例

4
2 4
1 3
3 12
3 4 5
1 5
5
2 10
15 4

算法1

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

由于题目数据最大为1e5；直接暴力枚举

时间复杂度

O（n）

参考文献

无

C++ 代码

#include<iostream>
#include<math.h>
using namespace std;
typedef long long LL;
LL n, x, a[100005];
int main()
{

    int T; cin >> T;
    while (T--) {
        cin >> n >> x;

        LL sum = 0x7fffffff,ans = 0;//定义一个sum来存储最小值
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            ans = LL(ceil((x*1.0) / (1.0*a[i])));//ceil的作用是向上取整

            if (ans == 1)//由于是向上取整的，可能a[i]>x的一步就超出了x的范围，这种情况是不行的。
            {
                if ((x * 1.0) / (1.0 * a[i]) != 1)
                    ans++;
            }
            sum = min(sum, ans);
        }
        cout << sum << endl;
    }
}