每日一题 | 土豪割草问题

昨日题解

每日一题 | 召唤兽问题

这道题的思路很简单，我们完全可以模拟一下这个英雄的魔法值的变化过程。在游戏开始的时候是n，然后每秒钟如果魔法值超过x则召唤一个召唤兽，否则什么也不做等待魔法恢复。那么我们只需要重复m次这个过程就可以统计出一共召唤出了多少个召唤兽。

这的确非常简单，但有一个很大的问题就是m的范围是10的九次方这个量级，显然我们用循环的方法是不行的，一定会超时。既然循环不行，那么就只能通过数学方法来计算了。

我们可以分成两种情况，第一种情况是每秒钟的恢复速度大于等于消耗速度，由于题目中给定了这个条件。所以只要魔法值的补充速度大于消耗速度，那么一定每秒钟都可以召唤召唤兽，所以答案就是m。

第二种情况是魔法的恢复速度不如消耗速度，这种情况就会棘手一些。但有一点可以肯定，就是在游戏的过程当中一定不会出现魔法值超过上限的情况。既然这样就好办了，我们可以写出一个方程，我们假设最后召唤出来的数量是h，可以得到：

n是游戏开始时的魔法量，(m-1)* y是游戏过程中总共能够恢复的魔法量，hx是消耗的魔法量。由于题目限定，最后剩余的魔法量一定要大于等于0，那剩下的就很简单了，我们把这几个值带进去算一下就得到结果了。但是这里有一个trick，有可能m很小，n很大，导致最后算出来的结果大于m，这也是不对的，因为m秒最多只能召唤出m个召唤兽，所以我们还需要和m取个最小值。

t = int(input())

for _ in range(t):
    line = input()
    n, m, x, y = int(line.split()[0]), int(line.split()[1]), int(line.split()[2]), int(line.split()[3])
    if y >= x:
        print(m)
    else:
        print(min((n + y * (m-1)) // x, m))

今日问题

割草问题

样例

- END -