题目详解

问题重述

你有一个烤架，初始温度为 $k$。有两种烤串：

• 类型1：要求起始温度 $\ge a$，烤后温度降低 $x$ 度。
• 类型2：要求起始温度 $\ge b$，烤后温度降低 $y$ 度。

你可以按任意顺序无限次烤这两种串（只要满足起始温度条件），问最多能烤多少串。

核心思路

关键观察：
烤完一串后，温度会下降。为了能烤更多的串，我们应该尽量让温度下降得慢，即优先烤降温幅度小的那种串。
因为温度越高，后续能烤的串就越多。

因此，一个自然的贪心策略是：

1. 先尽量多地烤降温幅度小的那种串（即 $\min(x, y)$ 对应的串），直到温度不足以再烤这种串。
2. 再尽量多地烤另一种串。

但是，两种串的起始温度要求可能不同（$a$ 和 $b$），所以我们需要尝试两种顺序：

• 顺序1：先烤类型1，再烤类型2。
• 顺序2：先烤类型2，再烤类型1。

取两种顺序中能烤的总数的最大值。

公式推导

假设当前温度是 $t$，要烤类型1（需求温度 $a$，降温 $x$），那么：

• 能烤的类型1的最大数量 = $\max\left(\left\lfloor \frac{t - a}{x} \right\rfloor + 1, 0\right)$
  或者用整数除法写法：$\max\left(\left\lfloor \frac{t - a}{x} \right\rfloor + 1, 0\right)$
  其中 $t-a$ 可能为负，所以需要与 $0$ 取最大值。

更精确的公式（代码中使用）：
能烤的数量 = $\max\left(\left\lfloor \frac{t - a + x}{x} \right\rfloor, 0\right)$
因为 $\left\lfloor \frac{t-a}{x} \right\rfloor + 1 = \left\lfloor \frac{t-a+x}{x} \right\rfloor$（整数除法下成立）。

例如：$t=10, a=3, x=2$
$\frac{10-3+2}{2} = \frac{9}{2} = 4.5$，下取整得 $4$，即能烤 $4$ 串。
验证：第1串：$10 \to 8$，第2串：$8 \to 6$，第3串：$6 \to 4$，第4串：$4 \to 2$（最后一串起始温度 $4 \ge 3$，烤后 $2$），再烤第5串时起始 $2 < 3$ 不行，所以确实是 $4$ 串。

算法步骤

对于一种顺序（先类型1，后类型2）：

1. 计算能烤的类型1数量：$cnt_1 = \max\left(\left\lfloor \frac{k - a + x}{x} \right\rfloor, 0\right)$
2. 更新温度：$k' = k - cnt_1 \times x$
3. 计算能烤的类型2数量：$cnt_2 = \max\left(\left\lfloor \frac{k' - b + y}{y} \right\rfloor, 0\right)$
4. 总数量 = $cnt_1 + cnt_2$

再计算先类型2后类型1的总数，取两者最大值。

示例验证

示例1：$k=10, a=3, b=4, x=2, y=1$

• 先1后2：
  $cnt_1 = \lfloor (10-3+2)/2 \rfloor = \lfloor 9/2 \rfloor = 4$，$k' = 10 - 4\times 2 = 2$
  $cnt_2 = \lfloor (2-4+1)/1 \rfloor = \lfloor -1 \rfloor = 0$（负数取0）
  总数 = $4$
• 先2后1：
  $cnt_2 = \lfloor (10-4+1)/1 \rfloor = \lfloor 7 \rfloor = 7$，$k' = 10 - 7\times 1 = 3$
  $cnt_1 = \lfloor (3-3+2)/2 \rfloor = \lfloor 2/2 \rfloor = 1$
  总数 = $8$
• 最大值 = $\max(4, 8) = 8$ ✅

示例2：$k=1, a=10, b=10, x=1, y=1$

• 先1后2：$cnt_1 = \lfloor (1-10+1)/1 \rfloor = \lfloor -8 \rfloor = 0$，$k'=1$，$cnt_2=0$，总数=0
• 先2后1：同理=0
• 最大值=0 ✅

复杂度

每个测试用例 $O(1)$，总复杂度 $O(t)$，完美通过 $t \le 10^4$。

总结

这道题的关键是认识到：因为温度只降不升，贪心地先烤降温小的串，且两种顺序都要尝试，就能得到最优解。公式中用整数除法处理“能烤的最大数量”非常巧妙。