自动搬运

查看原文

来自洛谷，原作者为

	RyanLi 跟着光，靠近光，成为光，散发光。

搬运于2025-08-24 21:16:04，当前版本为作者最后更新于2024-03-10 20:34:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Source & Knowledge

2024 年 3 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

有 $n$ 个球，其中有 $k$ 个橙色的，剩下的是绿的，求至少需要增加几个绿球才能使得 $\dfrac{k}{n} \le \dfrac{p}{q}$。

题目分析

因为 $n$、$k$、$p$ 和 $q$ 四个数都是已知的，因此我们设需要增加的绿球数量为 $x$，我们可以列出如下不等式：

$$\dfrac{k}{n + x} \le \dfrac{p}{q}$$

将 $x$ 用 $n$、$k$、$p$、$q$ 表示，可以得到：

$$x \ge \dfrac{q \times k}{p} - n$$

由于 $\dfrac{q \times k}{p}$ 的结果可能不是整数，而 $x$ 应该是满足这个不等式的最小整数，因此：

$$x = \left \lceil \dfrac{q \times k}{p} \right \rceil - n $$

其中 $\lceil a \rceil$ 表示对 $a$ 向上取整。例如，$a = 1.5$ 时，$\lceil a \rceil = 2$。

在 C++ 中，由于非负整数除法具有对结果向下取整（例如，$a = 1.5$ 时，$a$ 的向下取整为 $1$）的性质，所以有：

$$\left \lceil \dfrac{a}{b} \right \rceil = \left \lfloor \dfrac{a + b - 1}{b} \right \rfloor $$

其中 $\lfloor a \rfloor$ 表示对 $a$ 向下取整。代入我们上面推导出来的 $x$ 可以得到：

$$x = \left \lfloor \dfrac{q \times k + p - 1}{p} \right \rfloor - n $$

直接输出即可。

值得注意的是，如果 $\dfrac{k}{n} \le \dfrac{p}{q}$ 在一开始就成立（即不需要增加新的绿球），那么直接输出 $0$ 即可，无需进行上述计算。

cin >> n >> k >> p >> q;
if (1.0 * k / n <= 1.0 * p / q) cout << "0\n";
else cout << (q * k + p - 1) / p - n << '\n';

视频讲解

完整代码见视频题解