6-6 小红打怪

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

小红打怪

链接:https://ac.nowcoder.com/acm/contest/60456/D
来源:牛客网

时间限制:C/C++ 1秒
空间限制:C/C++ 262144K

题目描述

已知地图上有 \(n\) 只怪物,每只怪物的血量是 \(a_i\) ,攻击力是 \(b_i\)。小红准备去地图上探险杀怪,她的初始血量为 \(h\)。
小红有两个技能:

  1. 普通攻击:对一只怪物造成1点伤害。

  2. 强力攻击:对一只怪物造成2点伤害。

但是强力攻击是有冷却时间的。释放一个强力攻击后,需要2回合冷却(即释放2次普通攻击后)才能再次释放。
小红每次攻击后,若怪物没有死亡(即血量大于0),小红都会承受一次怪物攻击力的伤害。但是小红可以在战斗开始前喝血药,每个血药可以回复 \(k\) 点血量。也就算说,\(x\) 瓶血药可以将小红的初始血量提高到 \(h+x*k\)

已知每只怪物都是不可复活的,当小红血量为0或负数时死亡。小红选择打一个怪时,在该怪物被打死之前不会更换目标。

当小红打死一只怪物去寻找另外一只怪物的过程中,我们可以认为强力攻击的冷却已经恢复完毕。

请问,小红初始带了 \(x\) 瓶血药时,最多可以击杀多少只怪物?

上述问题会重复 \(q\) 次,每次询问都是独立的,小红初始的血瓶数量可能不同。

输入描述:

第一行输入三个正整数 \(n,h,k\) ,代表地图上怪物的数量、小红的初始血量,以及小红每瓶血药可以回复的血量。
接下来的 \(n\) 行,每行输入两个正整数 \(a_i\) 和 \(b_i\),代表地图上每只怪物的血量和攻击力。
接下来的一行输入一个正整数 \(q\),代表询问次数。
接下来的一行,输入 \(q\) 个正整数 \(x\),代表每次询问中小红携带的血药数量。
\(1\leq n,q,h,k,a_i,b_i,x \leq 10^5\)

输出描述:

输出一行 \(q\) 个正整数,代表小红携带 \(x\) 瓶血药时能击杀的最多怪物数量。

示例1

输入

3 1 2
5 1
5 2
3 2
3
1 2 3

输出

1 1 2

说明

第一只怪物小红需要攻击4次才能杀死,所以会被怪物打3下,掉血为\(1*3=3\)。
第二只怪物小红需要攻击4次才能杀死,所以会被怪物打3下,掉血为\(2*3=6\)。
第三只怪物小红需要攻击2次才能杀死,所以会被怪物打1下,掉血为\(2*1=2\)。
当小红携带1瓶血药时,可以先将血量回复至3点,然后击杀第三只怪物,剩余血量为1。
当小红携带2瓶血药时,无法击杀两只怪物。
当小红携带3瓶血药时,可以击杀第一只、第三只怪物。

2023暑假集训7月11日训练题

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2023-07-11 09:00
结束于
2023-07-11 11:30
持续时间
2.5 小时
主持人
参赛人数
20