B3942 题解

· · 题解

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';

视频讲解

完整代码见视频题解