公路旅行
时间限制: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