传统题 1000ms 256MiB

小胖打怪

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

经过一系列的闯关,小胖终于来到了关卡的尽头。没想到嘉琦大魔头居然还在尽头给她设置了障碍。

最后一关的障碍是这样,小胖面前出现了 $n$ 只怪物,每只怪物的血量为 $H_i$ ,但是小胖时间有限,她只能在 $t$ 回合的时间去击杀这些怪物,只有将怪物全部击杀完才能算胜利。

每回合小胖有两种攻击方式:

$1.$ 对一只怪物使用物理攻击,对其造成 $1$ 点伤害(物理攻击次数无上限);

$2.$ 对一只怪物使用魔法攻击“小胖冲撞”,对怪物造成 $X$ 点伤害(小胖冲撞次数上限为 $w$ 次);

小胖很仁慈,所以她不想使用太多次“小胖冲撞”。

请你最小化小胖冲撞的伤害 $X$,还能让小胖安全地过关。

如果伤害不管多大都无法通关时,请输出 $-1$ 。

输入格式

第一行 $T$,代表有 $T$ 组数据 ($1 \leq T \leq 100$)

每组数据由两行组成。

第一行包含三个整数 $n,t,w$ 分别表示怪物数量,回合数以及可以使用小胖冲撞的次数。( $1 \leq n \leq 10^5 ,1 \leq t \leq 10^5, 1\leq w \leq 10^5$ )

第二行包含 $n$ 个整数,第 $i$ 个数表示第 $i$ 只怪物的生命值 $H_i$。( $1 \leq H_i \leq 10^6$ )

数据保证 $ \sum{n} \leq 10^5$。

输出格式

对于每组数据,请在独立的行中输出一个整数 $X$ 代表能通关的最小伤害,若无法通关则输出 $-1$ ;

样例

2
3 4 3
5 3 1
4 5 3
5 3 4 3 
3
-1

提示

对于第一组数据,伤害为 $3$ 时我第一天选择使用小胖冲撞把第一只怪物打到$2$,第二天使用小胖冲撞把第一只怪物打死,第三天使用小胖冲撞打死第二只怪物,第四天使用物理攻击打死第三只怪物。可以证明 $3$ 是最小的可行解。

对于第二组数据,无论伤害设置多少,都无法在 $t$ 天内打死这几只怪物,输出 $-1$。

福建师范大学第24届低年级程序设计竞赛(重现赛)

未参加
状态
已结束
规则
ACM/ICPC
题目
7
开始于
2023-3-8 0:00
结束于
2023-12-24 15:00
持续时间
6999 小时
主持人
参赛人数
18