#761. 这是一道二分题
这是一道二分题
题目描述
到达目的地后,你想在新的星球上建立一个新的殖民地。由于这个星球上有很多山,而殖民地必须建在一个平坦的表面上,你决定用巨石把山压平(你还在做梦,所以这对你来说很有意义)。
你会得到一个数组,其中是第座山的高度,--你拥有的巨石的数量。
你将从第一座山顶开始逐一投掷巨石,巨石的滚动情况如下(我们假设当前山的高度为)。
如果,巨石将滚到下一座山。
如果,巨石将停止滚动并将山的高度增加()。
如果巨石到达最后一座山,它将落入垃圾收集系统并消失。
你想找到第块巨石的位置或确定它将落入废物收集系统。
输入格式
第一行包含一个整数--测试案例的数量。
每个测试用例由两行组成。每个测试案例的第一行包含两个整数和 (1≤n≤100;1≤k≤)--山的数量和巨石的数量。
第二行包含n个整数--山的高度。
保证所有测试案例的n之和不超过100。
输出格式
对于每个测试案例,如果第块巨石将落入收集系统,则打印。否则,打印第块巨石的位置。
样例
输入样例
4
4 3
4 1 2 3
2 7
1 8
4 5
4 1 2 3
3 1
5 3 1
输出样例
2
1
-1
-1
数据范围与提示
让我们模拟一下第一种情况。
第一块巨石从i=1开始;因为,所以它滚到,并在那里停下来,因为。
新的高度是。
第二块巨石从开始;因为,所以巨石滚到;因为,所以巨石滚到,因为,所以停在那里。
新的高度是。
第三块巨石从开始;因为,所以它滚到,因为而停在那里。
新的高度是。
每块巨石停在的位置如下。
在第二种情况下,所有块巨石都将停在第一座山的右边,使其高度从上升到。
第三种情况与第一种情况类似,但现在你要扔块巨石。前三个将以与第一个测试案例相同的方式滚动。之后,山的高度将等于,这就是为什么另外两块巨石将落入收集系统。
在第四种情况下,第一块也是唯一的一块巨石将直接落入收集系统中。