/ Vijos / 题库 /

公路旅行

公路旅行

时间限制:1秒  内存限制:256M


【问题描述】

  小H正在一条标有“有趣”的路标的公路上旅行。公路由数轴表示,并且小 H 从原点开始出发 \((x=0)\)。有 \(n\) 个路标被标在点 \(x_1,x_2,...,x_n\)。小 H 想要在日落前走尽可能多的点,就是说在 T 分钟内走完尽可能多的点。她每走一个单位距离要耗费 1 分钟。
  小 H 想按一种特别的顺序来访问这些路标。离原点越近的点越重要,她总是向没有访问且离原点最近的点前进。没有两个点会到原点同样的距离。请你帮助小 H 决定她在日落前最多能访问多少个路标。
  为了让你的程序更具普适性,需要实现对于不同的 \(T\),实现查询功能!

【输入格式】

  第一行是两个用空格隔开的整数 \(n\)。
  接下来的 \(n\) 行,每行包含一个单独的整数,表示一个路标在数轴上的位置\(x_i\)。
  再接是一个整数 \(m\) 行,表示有 \(m\) 次查询。然后的 \(m\) 行,每行一个整数 \(T\),表示询问小H用 \(T\) 分钟时间最多能访问的路标数。

【输出格式】

  包含 \(m\) 行,每行一个整数,表示每次查询的结果。

【输入输出样例】

 Input

5
10
-3
8
-7
1
3
25
6
3

 Output

4
2
1

【输入输出样例说明】

  对于第1个查询:小H有 25 分钟时间,他 可以依次访问 1,-3,-7 和 8,这时她共用去了 24 分钟。她不能再访问下一个路标 10,因为这样她用的总时间会是 26 分钟。
  对于第2个查询:小H有 5 分钟时间,他 可以依次访问 1,-3,这时她共用去了 5 分钟。她不能再访问下一个路标 -7,因为这样她用的总时间会是 9 分钟。

【数据限制】

  对于 \(70\%\) 的数据,\(1≤n≤50,000\),\(1≤m≤100\),。
  对于 \(100\%\) 的数据,\(1≤n≤50,000\),\(1≤m≤200000\),\(-100,000≤x_i≤100,000\),\(1≤T≤1,000,000,000\)。

【来源】

  Mr.he

信息

ID
2529
难度
(无)
分类
其他 | 排序二分查找 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
2
上传者