Problem A: 命运之弹
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:275
Solved:95
Description
在一处险恶的战场上,小 K 正面临着枪林弹雨的局面。现在有 $n$ 个子弹依次向他袭击而来。
上帝说过,冥冥之中定有天意,世上存在着一些虚无缥缈的运气。小 K 也有着一定的幸运值 $ v $。对于每颗子弹都有其对应的危险值 $a_i$, 当小 K 的幸运值不小于子弹的危险值,那么子弹将会被小 K 躲掉。否则,小 K 将会被击杀。
为了保护小 K 的安全,上帝偷偷给了小 K 一种魔法:
$x$ 次转瞬即逝的机会:小 K 将自己突然隐匿,该子弹的危险值变为 $0$。
现在上帝想请你来想想为了保护小 K 的安全,$x$ 至少要为多少?
由于 OJ 的输入输出较慢,程序中请加入 ios::sync_with_stdio(0), cin.tie(0); 将 endl 换成 '\n';
上帝说过,冥冥之中定有天意,世上存在着一些虚无缥缈的运气。小 K 也有着一定的幸运值 $ v $。对于每颗子弹都有其对应的危险值 $a_i$, 当小 K 的幸运值不小于子弹的危险值,那么子弹将会被小 K 躲掉。否则,小 K 将会被击杀。
为了保护小 K 的安全,上帝偷偷给了小 K 一种魔法:
$x$ 次转瞬即逝的机会:小 K 将自己突然隐匿,该子弹的危险值变为 $0$。
现在上帝想请你来想想为了保护小 K 的安全,$x$ 至少要为多少?
由于 OJ 的输入输出较慢,程序中请加入 ios::sync_with_stdio(0), cin.tie(0); 将 endl 换成 '\n';
Input
第一行输入一个整数 $t$ 。$(1 \le t \le 10 ^ 4)$ -- 表示测试样例的组数
接下来 $t$ 组,每组输入如下:
第一行输入两个整数 $n, q$ 。$(1 \le n, q \le 2 \cdot 10 ^ 5)$ -- 表示该组样例子弹数量以及查询次数
第二行输入 $n$ 个整数 $a_i$ 。$(1 \le a_i \le 10 ^ 9)$ -- 表示该组子弹的危险值
接下里 $q$ 行每行输入一个整数 $ v $ 。$(1 \le v \le 10 ^ 9)$ -- 表示该组小 K 的初始幸运值。
保证每一个测试点的 $n, q$ 的总和不超过 $2 \cdot 10 ^ 5$ 。
接下来 $t$ 组,每组输入如下:
第一行输入两个整数 $n, q$ 。$(1 \le n, q \le 2 \cdot 10 ^ 5)$ -- 表示该组样例子弹数量以及查询次数
第二行输入 $n$ 个整数 $a_i$ 。$(1 \le a_i \le 10 ^ 9)$ -- 表示该组子弹的危险值
接下里 $q$ 行每行输入一个整数 $ v $ 。$(1 \le v \le 10 ^ 9)$ -- 表示该组小 K 的初始幸运值。
保证每一个测试点的 $n, q$ 的总和不超过 $2 \cdot 10 ^ 5$ 。
Output
对于每一次的查询 $q$,输出一个整数表示本轮查询的最小的 $x$。
Sample Input Copy
2
6 3
2 6 4 4 1 9
2
7
1
3 2
2 4 6
100
4
Sample Output Copy
4
1
5
0
1