#P3017. 我是奶龙,别打我,呜呜呜!
我是奶龙,别打我,呜呜呜!
题目描述
有 个编号为 到 的奶龙在坐标轴上,第 个奶龙的生命值为 ,横坐标为 ,奶龙们的横坐标按编号升序排列。
你可以预先选定一个整数横坐标 ,并发动任意次数强度为 的攻击。
每次攻击后,第 个奶龙受到 点伤害;当奶龙生命值降到 及以下时,该奶龙就被击败。
注意: 在攻击前选定,选定后不能改变。
给定整数 ,求如何选择 ,使得能在最少的攻击次数内击败至少 个奶龙。
只需输出最少的攻击次数。
输入格式
- 第一行一个整数 ,表示测试用例数量。
- 每个测试用例:
- 第一行三个整数 $n, m, k\ (1 \le k \le n \le 10^4,\ 1 \le m \le 10^9)$。
- 第二行 个整数 。
- 第三行 个整数 $a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^9,\ a_i < a_{i+1},\ 1 \le i < n)$。
保证所有测试用例的和不超过
输出格式
对于每个测试用例,输出一行一个整数,表示击败至少 个敌人所需的最小攻击次数;
若不存在满足条件的 ,输出 。
样例
6
5 5 3
7 7 7 7 7
1 2 3 4 5
9 5 9
2 4 6 8 10 8 6 4 2
1 2 3 4 5 6 7 8 9
2 10 2
1 1
1 20
2 10 1
69696969 420420420
1 20
2 10 2
10 15
1 19
2 2 2
1000000000 1
1 3
2
2
-1
6969697
15
1000000000
样例解释:
在第一个测试用例中,选择是最优的。每次攻击,第一个敌人受到伤害,第二个敌人受到伤害,第三个敌人受到伤害,第四个敌人受到伤害,第五个敌人受到伤害。经过次攻击,第一个三个敌人将被击败。可以证明,无论选择哪个,都不可能在少于次攻击中击败个敌人。
在第二个测试用例中,我们必须击败所有个敌人。通过选择,所有九个敌人将在次攻击中被击败。
在第三个测试用例中,我们必须击败两个敌人。然而,可以证明没有选择的可以同时对两个敌人造成伤害,因此答案是。
在第四个测试用例中,选择将使我们能够在次攻击中击败第一个敌人。
在第五个测试用例中,选择将使每个敌人在每次攻击中受到伤害。两个敌人将在次攻击中被击败。
相关
在下列比赛中: