CHDOJ
首页
题库
题单
比赛
评测
用户
讨论
帮助
工具
云剪贴板
树图画板
代码对比
登录
注册
3062: 彩虹岛寻宝
时间限制:1000 ms
内存限制:128 MB
上传者:
提交:7
通过:5
提交
提交记录
讨论
统计
题目描述
历经千辛万苦,旺旺终于找到了大魔王的宝箱。
宝箱内有$n$件宝物,每一件宝物都有一个编号。
大魔王的宝藏十分神奇,对于一组宝物,其重量被定义为:编号最大的宝物的编号与编号最小的宝物的编号的差值。比如说一组宝藏的编号为$8,5,9$,这组宝藏的重量就为$4~(9-5=4)$。
彩虹岛的小仙女旺旺想尽可能拿走更多件的宝物,因为她想卖一些宝物去请彩虹岛ACM集训队的所有队员吃饭,但是她只有一个承重能力为$x$的包包,即旺旺如果拿走了一些宝物,他们的重量是$y$(也就是说被拿走的宝物中最大编号与最小编号的差为$y$),而且旺旺的包包承重能力$x$大于等于$y$,那么旺旺就可以拿走这组宝物,否则不行。
你能告诉她,她最多能拿走多少件宝物吗?
输入格式
输入的第一行包含一个正整数$T(1\le T \le 10)$,表示测试样例数。
每一组测试样例第一行包含两个整数$n(1 \le n \le 2\times 10^5)$和$x(1\le x\le 10^9)$,分别代表宝物的数量与旺旺包包的承重能力。
接下来一行包含$n$个用空格分开的整数$a_i(1\le a_i \le 10^9)$,表示每一件宝物的编号。
输出格式
对于每组测试样例输出一个数字$number$,表示旺旺最多能带走多少件宝物。
输入样例
复制
2 3 2 1 2 2 9 100 1002 1003 1001 5 3 6 4 1000 1000
输出样例
复制
3 5
数据范围与提示
分类标签
2019年长安大学第六届程序设计竞赛新生赛