最新消息: USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。

3773. 兔子跳

IT圈 admin 2浏览 0评论

3773. 兔子跳

AcWing 3773. 兔子跳

题目:

一只兔子位于二维平面的原点 (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

代码:

#include <cstdio>
#include <iostream>
using namespace std;int main()
{int T;cin>>T;while (T--){int n, Max = 1, flag = 0, x, a;cin>>n>>x;while (n--){scanf("%d",&a);if (a == x) flag = 1;Max = max(a,Max);}if (flag)puts("1");//当刚好有距离等于x时,只需要跳一步即可到达else if (Max > x) puts("2");//当Max大于x时,最多只需要跳两步即可到达else printf("%d\n", (x+Max-1)/Max);//向上取整,跳x/Max - 1步时,即在最后两步之前只需要跳直线,//在最后两步跳等腰三角形,两条腰长为Max,底边长小于2Maxreturn 0;
}

3773. 兔子跳

AcWing 3773. 兔子跳

题目:

一只兔子位于二维平面的原点 (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

代码:

#include <cstdio>
#include <iostream>
using namespace std;int main()
{int T;cin>>T;while (T--){int n, Max = 1, flag = 0, x, a;cin>>n>>x;while (n--){scanf("%d",&a);if (a == x) flag = 1;Max = max(a,Max);}if (flag)puts("1");//当刚好有距离等于x时,只需要跳一步即可到达else if (Max > x) puts("2");//当Max大于x时,最多只需要跳两步即可到达else printf("%d\n", (x+Max-1)/Max);//向上取整,跳x/Max - 1步时,即在最后两步之前只需要跳直线,//在最后两步跳等腰三角形,两条腰长为Max,底边长小于2Maxreturn 0;
}

与本文相关的文章

发布评论

评论列表 (0)

  1. 暂无评论